题目

#include<bits/stdc++.h>
using namespace std;
struct edge{
    long long v,w;
}; 
long long n,m,s;
vector<edge> g[110001];
long long dis[1001001],cnt[1001001],inq[1001001];
bool spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	queue<int> que;
	que.push(s);
	inq[s] = 1;
	dis[s] = 0;
	while(!que.empty()){
		int u = que.front();
		que.pop();
		inq[u] = 0; 
		for(int i = 0;i < g[u].size();i++){
			int v = g[u][i].v, w = g[u][i].w;
			if(dis[u]+w< dis[v]){
				dis[v] = dis[u]+w;
				if(!inq[v]){
					inq[v] = 1;
					que.push(v);
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i = 1;i <= m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back(edge{v,w});
	}
	spfa(s);
	for(int i = 1;i <= n;i++){
		cout<<dis[i]<<" ";
	}
}