oj.uz

답안 #9247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9247 2014-09-28T05:00:42 Z veckal Your life (kriii2_Y) C++14
4 / 4
 88 ms 7272 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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