Submission #9226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9226	2014-09-28T04:51:58 Z	kkjjkk	Your life (kriii2_Y)	C++	4 / 4	96 ms	10876 KB

Y

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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