用户

个人简介

#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s,u,v,w,cnt;
int queue[100005],head[10005],dis[10005];
bool vis[10005];
struct edge{
int to;
int next;
int val;
}a[500005];
void add(int u,int v,int w)
{
a[++cnt].to=v;
a[cnt].val=w;
a[cnt].next=head[u];
head[u]=cnt;
}
void spfa()
{
int u,l=0,r=1;
queue[1]=s;
vis[s]=1;
dis[s]=0;
while(l<r)
{
u=queue[++l];
vis[u]=0;
for(int i=head[u];i;i=a[i].next)
{
if(dis[u]+a[i].val<dis[a[i].to])
{
dis[a[i].to]=dis[u]+a[i].val;
if(vis[a[i].to]==0)
{
vis[a[i].to]=1;
queue[++r]=a[i].to;
}
}
}
}
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;++i)
dis[i]=INF;
dis[s]=0;
for(int i=1;i<=m;++i)
{
cin>>u>>v>>w;
add(u,v,w);
}
spfa();
for(int i=1;i<=n;++i)
{
if(dis[i]==INF)
cout<<2147483647<<" ";
else
cout<<dis[i]<<" ";
}
return 0;
}