Submission #9632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
9632	2014-09-28T07:45:30 Z	carl111	Your life (kriii2_Y)	C++	4 / 4	100 ms	7600 KB

Y

#include <vector>
#include <queue>
#include <stdio.h>

using namespace std;


vector< vector<int> > graph;


vector<int> dijkstra(int V, int src)
{
	vector<int> dist(V,0x7fffffff);
	dist[src] = 0;
	priority_queue<pair<int,int> > myqueue;
	myqueue.push(make_pair(0,src));

	while(!myqueue.empty())
	{
		int cost = -myqueue.top().first;
		int here = myqueue.top().second;

		myqueue.pop();

		if(cost > dist[here])
		{
			continue;
		}
		for(int i=0;i<graph[here].size();i++)
		{
			int there = graph[here][i];
			int nextDist = cost + 1;

			if(dist[there] > nextDist)
			{
				dist[there] = nextDist;
				myqueue.push(make_pair(-nextDist,there));
			}
		}
	}
	return dist;
}

int main()
{
	int N,M;
	scanf("%d%d",&N,&M);
	if(M==0)
	{
		if(N==1)
		{
			printf("0\n");
		}
		else
		{
			printf("-1\n");
		}
	}
	else
	{
		graph.resize(N);
		for(int i=0;i<M;i++)
		{
			int f,t;
			scanf("%d%d",&f,&t);
			f-=1;t-=1;
			graph[f].push_back(t);
		}
		vector<int> k = dijkstra(N,0);
		if(k[N-1] == 0x7fffffff)
		{
			printf("-1\n");
		}
		else
		{
			printf("%d\n",k[N-1]);
		}
	}
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	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	16 ms	1768 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1240 KB	Output is correct
2	Correct	40 ms	7012 KB	Output is correct
3	Correct	52 ms	7012 KB	Output is correct
4	Correct	40 ms	7012 KB	Output is correct
5	Correct	52 ms	7012 KB	Output is correct
6	Correct	40 ms	7012 KB	Output is correct
7	Correct	28 ms	7012 KB	Output is correct
8	Correct	100 ms	7600 KB	Output is correct
9	Correct	40 ms	7012 KB	Output is correct
10	Correct	84 ms	6748 KB	Output is correct