1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<queue> 6 using namespace std; 7 typedef long long LL; 8  9 const int N=10010,M=500010;10 const LL INF=2147483647;11 int n,m,st,len=0;12 int vis[N],last[N];13 LL dis[N];14 struct edge{int x,y,next;LL d;}a[2*M];15 queue<int> q;16 17 void ins(int x,int y,LL d)18 {19     a[++len].x=x,a[len].y=y,a[len].d=d;20     a[len].next=last[x],last[x]=len;21 }22 void spfa()23 {24     for (int i=1;i<=n;i++) dis[i]=INF;25     memset(vis,0,sizeof(vis));26     while (!q.empty()) q.pop();27     dis[st]=0, vis[st]=1;28     q.push(st);29     while (!q.empty())30     {31       int x=q.front();32       q.pop(); vis[x]=0;33       for (int i=last[x];i;i=a[i].next)34       {35         int y=a[i].y;36         if (dis[x]+a[i].d<dis[y])37         {38           dis[y]=dis[x]+a[i].d;39           if (!vis[y]) vis[y]=1, q.push(y);40         }41       }42     }43 }44 int main()45 {46     scanf("%d%d%d",&n,&m,&st);47     int x,y; LL d;48     memset(last,-1,sizeof(last));49     for (int i=1;i<=m;i++)50     {51       scanf("%d%d%lld",&x,&y,&d);52       ins(x,y,d);53     }54     spfa();55     for (int i=1;i<=n;i++)56       printf("%lld ",dis[i]);57     printf("\n");58     return 0;59 }