oj.uz

답안 #9226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9226 2014-09-28T04:51:58 Z kkjjkk Your life (kriii2_Y) C++
4 / 4
 96 ms 10876 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<queue>
#include<deque>
using namespace std;

const int MAX_V = 200005;
const int INF = 987654321;

int V;
vector<pair<int, int> > adj[MAX_V];

vector<int> dijkstra(int src) {
	vector<int> dist(V, INF);
	dist[src] = 0;
	priority_queue<pair<int, int> > pq;
	pq.push(make_pair(0, src));
	while(!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if(dist[here] < cost) continue;
		for(int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;
			if(dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
	if(dist[V - 1] == INF) printf("-1");
	else printf("%d", dist[V - 1]);
	return dist;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    V = n + 1;
    for(int i = 0; i < m; i++) {
         int a, b;
         scanf("%d %d", &a, &b);
         adj[a].push_back(make_pair(b, 1));
    }
    dijkstra(1);
}

Subtask #1
1.0 / 1.0

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

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6756 KB Output is correct
2 Correct 40 ms 9792 KB Output is correct
3 Correct 52 ms 9924 KB Output is correct
4 Correct 52 ms 9792 KB Output is correct
5 Correct 48 ms 9924 KB Output is correct
6 Correct 48 ms 9792 KB Output is correct
7 Correct 28 ms 9792 KB Output is correct
8 Correct 96 ms 10876 KB Output is correct
9 Correct 48 ms 9792 KB Output is correct
10 Correct 72 ms 10188 KB Output is correct