如题

	#include<bits/stdc++.h>
	using namespace std;
	#define int long long
	int n,m,cnt=1,head[1000005],ans[1000005];
	int s;
	struct edge{
		int to,w,next;
	}mapp[1000005];
	void addedge(int a,int b,int c){
		mapp[cnt].next=head[a];
		mapp[cnt].to=b;
		mapp[cnt].w=c;
		head[a]=cnt;
		cnt++;
	}
	bool view[1000005];
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	void dijk(){
		while(!q.empty()){
			pair<int,int> qwq=q.top();
			q.pop();
			//cout<<ans[s];
			view[qwq.second]=1;
		//	cout<<qwq.second<<" "<<qwq.first<<endl; 
			for(int i=head[qwq.second];i!=0;i=mapp[i].next){
		//		cout<<mapp[i].to<<" "<<mapp[i].w<<endl;
			
					if(mapp[i].w+ans[qwq.second]<ans[mapp[i].to]){
						
						
						ans[mapp[i].to]=mapp[i].w+ans[qwq.second];
						q.push(make_pair(ans[mapp[i].to],mapp[i].to));
						if(!view[mapp[i].to]){
							q.push(make_pair(ans[mapp[i].to],mapp[i].to));
						}
					}
				
			}
		}
	}
	signed main(){
	    //freopen(".in","r",stdin);
		//freopen(".out","w",stdout);
		scanf("%lld%lld%lld",&n,&m,&s);
		for(int i=0;i<=n;i++){
			ans[i]=2147483647;
		}
		ans[s]=0;
		for(int i=0;i<m;i++){
			int ar,w,e;
			scanf("%lld%lld%lld",&ar,&w,&e);
			addedge(ar,w,e);
			if(ar==s&&w!=s){
				ans[w]=e;
			
				
				q.push(make_pair(e,w));
			}
		}
		view[s]=1; 
		dijk();
		for(int i=1;i<=n;i++){
			printf("%lld ",ans[i]);
		}
		return 0;
	}
	

yysy我这份代码跑P4779T了仨点