oj.uz

답안 #9632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
9632 2014-09-28T07:45:30 Z carl111 Your life (kriii2_Y) C++
4 / 4
 100 ms 7600 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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