Несложная задача на поиск в ширину

[FIDE]

Здравствуйте. Есть задачка не очень сложная на поиск в ширину.
http://codeforces.com/contest/602/problem/C
Решение задачи заключается в том что один путь идет прямо из вершины 1 в вершину N("для любой пары различных городов x и y между ними есть двунаправленная автомобильная дорога тогда и только тогда, когда между ними нет железнодорожного перегона") и нам не нужно думать о том чтобы пути не пересекались. В итоге нужно по сути просто написать BFS. У меня есть код но к сожалению на одном тесте не проходит из-за превышения лимита памяти.

#include <iostream>
#include <queue>

using namespace std;

struct path
{
	int v,cost;
};

int main()
{
	int n,m;
	cin>>n>>m;
	vector < vector <bool> > a(n,vector<bool>(n,false));
	for (int i=0;i<m;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x-1][y-1]=true;a[y-1][x-1]=true;
	}
	if (a[0][n-1])
	for (int i=0;i<n;i++)
	 for (int j=0;j<n;j++) a[i][j]=!a[i][j];
	queue <path> q;
	q.push({0,0});
	vector <bool> used(n,false);
	int res=-1;
	while (!q.empty())
	{
		path k=q.front();
		q.pop();
		if (k.v==n-1)
		{
			res=k.cost;
			break;
		}
		used[k.v]=true;
		for (int i=0;i<n;i++)
		 if (a[k.v][i] && !used[i])	q.push({i,k.cost+1});	
	}
	cout<<res;
}

Вроде должно вложиться по памяти. Подскажите, что не так. Спасибо.

[FIDE]

Неужели никто не знает в чем проблема?

[Stilet]

Я в ширь решать такие задачки не умею

[FIDE]

Да задача-то решена фактически, надо только с памятью придумать что-то. Хотя я до сих пор не понимаю как я мог превысить ограничения памяти.

[Poma][a]

Ни разу не решена.

[FIDE]

Спасибо Капитан Понятно что раз на тесте не проходит то не решена, но лучше бы ты что-то по теме написал...

Или лучше вообще пройди мимо этой темы...

[Poma][a]

Да пожалста.

if (a[k.v][i] && !used[i]) { q.push({ i,k.cost + 1 }); used[i] = true; }

[FIDE]

Точно! Надо внимательнее мне быть... Спасибо огромное.