1

#include<bits/stdc++.h> using namespace std; int n,m,s; struct node{ int to; int dis; }; vector a[10001]; long long dis[10001]; int vis[10001]; void spfa(){ queue q;//spfa队列 //1.初始化dis for(int i=1;i<=n;i++)dis[i]=2147483647; dis[s]=0; q.push(s); while(!q.empty()){ int x=q.front(); //遍历当前的点x的所有邻点 for(int i=0;i<a[x].size();i++){ int y=a[x][i].to; int z=a[x][i].dis; if(dis[y]>dis[x]+z){ dis[y]=dis[x]+z; if(vis[y]==0){ q.push(y); vis[y]=1; } } } q.pop(); vis[x]=0; } } int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; //邻接表存有向图 a[u].push_back(node{v,w}); } spfa();

for(int i=1;i<=n;i++)cout<<dis[i]<<' '; }