Submission #9632

#	Time	Username	Problem	Language	Result	Execution time	Memory
9632		carl111	Your life (kriii2_Y)	C++98	4 / 4	100 ms	7600 KiB

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 / 1
• Subtask 2: 3 / 3