Submission #9340

#	Time	Username	Problem	Language	Result	Execution time	Memory
9340		YesUjam	Your life (kriii2_Y)	C++98	4 / 4	92 ms	7568 KiB

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