1 #include <iostream> 2 #include <algorithm> 3 #include <cmath> 4 #include <cstdio> 5 #include <cstring> 6 #include <cstdlib> 7 using namespace std; 8 int value[10010],to[10010],next[10010]; 9 int head[10010],total; 10 int book[10010]; 11 int dis[10010]; 12 int n,m; 13 void adl(int a,int b,int c) 14 { 15 total++; 16 to[total]=b; 17 value[total]=c; 18 next[total]=head[a]; 19 head[a]=total; 20 } 21 void dijkstra(int u) 22 { 23 memset(dis,88,sizeof(dis)); 24 memset(book,0,sizeof(book)); 25 dis[u]=0; 26 for(int i=1;i<=n;i++) 27 { 28 int start=-1; 29 for(int j=1;j<=n;j++) 30 if(book[j]==0 && (dis[start]>dis[j] || start==-1)) 31 start=j; 32 book[start]=1; 33 for(int e=head[start];e;e=next[e]) 34 dis[to[e]]=min(dis[to[e]],dis[start]+value[e]); 35 } 36 } 37 int main() 38 { 39 cin>>n>>m; 40 for(int i=1;i<=m;i++) 41 { 42 int a,b,c; 43 cin>>a>>b>>c; 44 adl(a,b,c); 45 } 46 dijkstra(1); 47 for(int i=1;i<=n;i++) 48 cout<<dis[i]<<" "; 49 }