답안 #9340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9340	2014-09-28T05:42:58 Z	YesUjam	Your life (kriii2_Y)	C++	4 / 4	92 ms	7568 KB

Y

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
#define M 100005
struct me{
	int x,y;
	bool operator < (const me &A)const{
		return y>A.y;
	}
};
me t,qu;
priority_queue< me > heap;
vector<int> a[M];
int n,m,re[M];
void dijkstra(int x){
	int i;
	t.x=x; t.y=re[x]; heap.push(t);
	while(1){
		if(heap.empty()) break;
		t=heap.top();
		heap.pop();
		for(i=0;i < a[t.x].size();i++){
			if(re[a[t.x][i]]==0 || re[a[t.x][i]]>re[t.x]+1){
				re[a[t.x][i]]=re[t.x]+1;
				qu.x=a[t.x][i]; qu.y=re[a[t.x][i]];
				heap.push(qu);
			}
		}
	}
}
int main()
{
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		a[x].push_back(y);
	}
	dijkstra(1);
	if(re[n]==0) printf("-1\n");
	else printf("%d\n",re[n]);
	return 0;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3944 KB	Output is correct
2	Correct	36 ms	6980 KB	Output is correct
3	Correct	56 ms	6980 KB	Output is correct
4	Correct	44 ms	6980 KB	Output is correct
5	Correct	60 ms	6980 KB	Output is correct
6	Correct	32 ms	6980 KB	Output is correct
7	Correct	36 ms	6980 KB	Output is correct
8	Correct	92 ms	7568 KB	Output is correct
9	Correct	52 ms	6980 KB	Output is correct
10	Correct	64 ms	6716 KB	Output is correct