如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
主要还是再打一遍最短路，这种算法我用的不多。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 inline int read() 5 { int x=0;bool f=0;char ch=getchar(); 6 while(!isdigit(ch)){ f=(ch==45);ch=getchar();} 7 while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 8 return f?(~x+1):x; 9 } 10 #define man 500010 11 int n,m,st; 12 int head[man<<2],num=0; 13 struct edge 14 { int next,to,dis;}e[man<<2]; 15 inline void add(int from,int to,int dis) 16 { e[++num].next=head[from]; 17 e[num].to=to; 18 e[num].dis=dis; 19 head[from]=num; 20 } 21 int dis[man<<2]; 22 bool vis[man<<2]; 23 inline void djikstra(int s) 24 { int turn=n-1; 25 for(int i=1;i<=n;i++) dis[i]=2147483647,vis[i]=0; 26 for(int i=head[s];i;i=e[i].next) 27 dis[e[i].to]=e[i].dis; 28 dis[s]=0; 29 while(turn--) 30 { int mx=2147483647; 31 int t=0; 32 for(int i=1;i<=n;i++) 33 if(!vis[i]&&dis[i]<mx) 34 mx=dis[i],t=i; 35 if(t==0||mx==2147483647) break; 36 vis[t]=1; 37 for(int i=head[t];i;i=e[i].next) 38 if(dis[e[i].to]>dis[t]+e[i].dis) 39 dis[e[i].to]=dis[t]+e[i].dis; 40 } 41 } 42 int main() 43 { n=read(),m=read(),st=read(); 44 for(int i=1;i<=m;i++) 45 { int x=read(),y=read(),z=read(); 46 add(x,y,z); 47 } 48 djikstra(st); 49 for(int i=1;i<=n;i++) 50 printf("%d ",dis[i]); 51 putchar(' '); 52 return 0; 53 }