rt,求其正确性

P4779 P3371

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<map>
#define int long long
using namespace std;
int n,m,s,h[100004],d[100004],dis[100004],ans[100004],ec;
struct Edge{
	int u,v,nxt,w;
}e[200004];
inline void Add(int u,int v,int w)
{
	d[v]++,e[++ec].u=u,e[ec].v=v,e[ec].nxt=h[u],e[ec].w=w,h[u]=ec;
}
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> >que;
main()
{
	scanf("%lld %lld %lld",&n,&m,&s);
	memset(dis,-1,sizeof dis);
	for(int i=1,u,v,w;i<=m;i++)scanf("%lld %lld %lld",&u,&v,&w),Add(u,v,w);
	que.push(P(0,s));
	while(!que.empty())
	{
		int t=que.top().first,i=que.top().second;
		que.pop();
		if(dis[i]>=0)continue;
		dis[i]=t;
		for(int j=h[i];j;j=e[j].nxt)
		{
			int v=e[j].v,w=e[j].w;
			que.push(P(t+w,v));
		}
	}
	for(int i=1;i<=n;i++)printf("%lld ",dis[i]);
	return 0;
}