迪杰斯特拉求调，P4779标准版已过，弱化版WA#2#9#10

#include <bits/stdc++.h>
using namespace std;
long long n,m,s,id[500000],ans[500000];

struct T{
	long long you,quan;
};

vector <T> q[500005];

bool operator<(T x,T y){
	return x.quan>y.quan;
}

priority_queue <T> p;

int main(){
    long long MA=99999999999;
//	freopen("P4779_1.in","r",stdin);
//	freopen("1.txt","w",stdout);
	cin >>n>>m>>s;
	for(long long i=1;i<=n;i++){
		ans[i]=MA;
	}
	for(long long i=1;i<=m;i++){
		long long u,v,w;
		cin >>u>>v>>w;
		q[u].push_back((T){v,w});
		id[i]=0;
	}
	p.push((T){s,0});
	ans[s]=0;
//	id[s]=1;
//	long long pd=1;
	while(p.empty()==0){
		T d=p.top();
		long long dd=d.you;
		long long ddd=d.quan;
		p.pop();
		if(id[dd]==1){
//			pd++;
			continue;
		}
		id[dd]=1;
		for(long long i=0;i<q[dd].size();i++){
			long long q1=q[dd][i].you;
			long long q2=q[dd][i].quan;
			if(ans[q1]>ans[dd]+q2){
				ans[q1]=ans[dd]+q2;
//				if(id[q1]!=1){
					p.push((T){q1,ans[q1]});
//				}
			}
		}
	}
	ans[s]=0;
	for(long long i=1;i<=n;i++){
        if(ans[i]==MA){
            cout <<"2147483647 ";
            continue;
        }
		cout <<ans[i]<<" ";
	}
	return 0;
}