Submission #9664

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9664	2014-09-28T07:58:34 Z	sior	Your life (kriii2_Y)	C++	4 / 4	252 ms	8732 KB

Y

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <queue>
#define MAX	100002

using namespace std;
vector<int> vec[MAX];
int dist[MAX];
bool visited[MAX] = { 0, };
queue<int> q;

int main()
{
	memset(dist, -1, sizeof(dist));

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;	// 연결
		a--; b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	q.push(0);
	visited[0] = true;
	dist[0] = 0;
	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int i = 0; i < vec[here].size(); i++) {
			if (!visited[vec[here][i]]) {
				visited[vec[here][i]] = true;
				q.push(vec[here][i]);
				dist[vec[here][i]] = dist[here] + 1;
			}
		}
	}
	cout << dist[n - 1] << endl;

	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	4508 KB	Output is correct
2	Correct	120 ms	7544 KB	Output is correct
3	Correct	180 ms	7544 KB	Output is correct
4	Correct	144 ms	7544 KB	Output is correct
5	Correct	168 ms	7544 KB	Output is correct
6	Correct	124 ms	7676 KB	Output is correct
7	Correct	108 ms	7676 KB	Output is correct
8	Correct	252 ms	8732 KB	Output is correct
9	Correct	156 ms	7544 KB	Output is correct
10	Correct	244 ms	8728 KB	Output is correct