90pts求条...

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 +5;
int n,m,start,i,j,k;
int u[maxn],v[maxn],w[maxn],first[maxn],nex[maxn],dis[maxn],book[maxn],que[maxn],head=1,tail=1;
int main(void)
{
	cin>>n>>m>>start;
	for(int i=1;i<=n;i++) dis[i]=999999;
	for(int i=1;i<=n;i++) first[i]=-1;
	dis[start]=0;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		nex[i]=first[u[i]];
		first[u[i]]=i;
	}
	que[tail]=start;
	tail++;
	book[start]=1;
	while(head<tail){
		k=first[que[head]];
		while(k!=-1){
			if(dis[v[k]]>dis[u[k]]+w[k]){
				dis[v[k]]=dis[u[k]]+w[k];
				if(book[v[k]]==0){
					que[tail]=v[k];
					tail++;
					book[v[k]]=1;
				}
			}
			k=nex[k];
		}
		book[que[head]]=0;
		head++;
	}
	for(int i=1;i<=n;i++)
    {
        if(dis[i]==999999)
        {
            cout<<2147483647;
        }
        else
        {
            cout<<dis[i]<<" ";
        }
	}
	return 0;
}