题目

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge{
	int v,w;
};
vector<edge> g[1000100];
long long INF = 2147483647;
long long dis[1001000];
bool vis[1001000];
void dijk(int s){
	memset(dis,INF,sizeof(dis));
	dis[s] = 0;
	for(int i =0;i < n;i++){
		int u = 0;
		for(int v = 1;v <= n;v++){
			if(!vis[v] && (u == 0 || dis[v]<dis[u]))u = v;
		}
		vis[u] = 1;
		for(int j = 0;j < g[u].size();j++){
		    int v = g[u][j].v,w = g[u][j].w;
		    if(!vis[v]&&dis[u]+w<dis[v]){
		    	dis[v] = dis[u]+w;
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(edge{v,w});
	}
	dijk(s);
	for(int i = 1;i <= n;i++){
		cout<<(dis[i] == INF ? pow(2,31)-1:dis[i])<<" ";
	}	
	return 0;
}