Submission #9247

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9247	2014-09-28T05:00:42 Z	veckal	Your life (kriii2_Y)	C++14	4 / 4	88 ms	7272 KB

Y

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int INF = 987654321;

int n, m;
vector<vector<int>> edge;

int dijkstra() {
	vector<int> dist(n, -1);
	vector<bool> discovered(n);
	discovered[0] = 1;
	dist[0] = 0;
	queue<int> q;
	q.push(0);
	while(!q.empty()) {
		int here = q.front();
		q.pop();
		for (int i=0; i<edge[here].size(); ++i) {
			int there = edge[here][i];
			if (discovered[there]) continue;
			dist[there] = dist[here] + 1;
			discovered[there] = 1;
			q.push(there);
		}
	}
	return dist[n-1];
}

int main() {
	scanf("%d%d", &n, &m);
	edge = vector<vector<int>>(n);
	for (int i=0; i<m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		edge[x].push_back(y);
	}
	printf("%d\n", dijkstra());
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	0 ms	1240 KB	Output is correct
3	Correct	0 ms	1240 KB	Output is correct
4	Correct	0 ms	1240 KB	Output is correct
5	Correct	0 ms	1240 KB	Output is correct
6	Correct	0 ms	1240 KB	Output is correct
7	Correct	0 ms	1240 KB	Output is correct
8	Correct	0 ms	1240 KB	Output is correct
9	Correct	0 ms	1240 KB	Output is correct
10	Correct	24 ms	1768 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3972 KB	Output is correct
2	Correct	36 ms	7008 KB	Output is correct
3	Correct	60 ms	7008 KB	Output is correct
4	Correct	60 ms	7008 KB	Output is correct
5	Correct	60 ms	7008 KB	Output is correct
6	Correct	28 ms	7008 KB	Output is correct
7	Correct	32 ms	7008 KB	Output is correct
8	Correct	88 ms	7272 KB	Output is correct
9	Correct	52 ms	7008 KB	Output is correct
10	Correct	76 ms	6744 KB	Output is correct