代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define int long long
int n,m,s;
struct node{
	int y,w;
};
vector<node> nbr[N];
bool vis[N];
int dis[N];
void SPAF(int start){
	queue<int>q;
	memset(vis,false,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[start]=0;
	q.push(start);
	vis[start]=1;	
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=0;i<nbr[x].size();i++){
			int w=nbr[x][i].w,nxt=nbr[x][i].y;
			if(dis[nxt]>dis[x]+w){
				dis[nxt]=dis[x]+w;
				if(vis[x]==0){
					vis[nxt]=1;
					q.push(nxt);
				}
			}
		}
	}
}
signed main(){
	cin >> n >> m >> s;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin >> x >> y >> z;
		nbr[x].push_back((node){y,z});
	}
	SPAF(s);
	for(int i=1;i<=n;i++){
		if(dis[i]==0x3f3f3f3f){
			cout << 2147483647 << " ";
		}else{
			cout << dis[i] << " ";
		}
	}
	return 0;
}