oj.uz

답안 #9227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9227 2014-09-28T04:53:01 Z shashack Your life (kriii2_Y) C++
4 / 4
 204 ms 7188 KB 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main(){
	int N, M; cin >> N >> M;
	vector<vector<int> >adj(N+1);
	vector<bool> visit(N + 1, false);
	for (int i = 0; i < M; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
	}
	priority_queue <pair<int, pair<int, int> > >pq;
	pq.push(make_pair(0, make_pair(0, 1)));

	while (true){
		if (pq.empty()){
			cout << -1 << endl;
			break;
		}
		int val = -pq.top().first;
		int u = pq.top().second.first;
		int v = pq.top().second.second;
		pq.pop();

		for (int i = 0; i < adj[v].size(); i++){
			if (!visit[adj[v][i]]) {
				if (adj[v][i] == N) {
					cout << val + 1 << endl;
					return 0;
				}
				visit[adj[v][i]] = true;
				pq.push(make_pair(-1 * (val + 1), make_pair(v, adj[v][i])));
			}
		}
	}
	return 0;
}

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 1676 KB Output is correct
2 Correct 0 ms 1676 KB Output is correct
3 Correct 0 ms 1676 KB Output is correct
4 Correct 0 ms 1676 KB Output is correct
5 Correct 0 ms 1676 KB Output is correct
6 Correct 0 ms 1676 KB Output is correct
7 Correct 0 ms 1676 KB Output is correct
8 Correct 0 ms 1676 KB Output is correct
9 Correct 0 ms 1676 KB Output is correct
10 Correct 64 ms 2204 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4020 KB Output is correct
2 Correct 96 ms 7056 KB Output is correct
3 Correct 168 ms 7056 KB Output is correct
4 Correct 124 ms 7056 KB Output is correct
5 Correct 168 ms 7056 KB Output is correct
6 Correct 100 ms 7056 KB Output is correct
7 Correct 100 ms 7056 KB Output is correct
8 Correct 204 ms 7188 KB Output is correct
9 Correct 128 ms 7056 KB Output is correct
10 Correct 204 ms 6792 KB Output is correct