POJ 1734

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 const int inf=10000001;
 8 const int MAXN=105;
 9 int n,m,num,minc;
10 int map[MAXN][MAXN],dis[MAXN][MAXN];
11 int fa[MAXN][MAXN],path[MAXN];
12 
13 void init(){
14     for(int i=1;i<=n;i++){
15         for(int j=1;j<=n;j++){
16             map[i][j]=dis[i][j]=inf;
17             fa[i][j]=i;
18         }
19         map[i][i]=dis[i][i]=0;
20     }
21 }
22 
23 void floyd(){
24     int tmp,p;
25     minc=inf;
26     for(int k=1;k<=n;k++){
27         for(int i=1;i<k;i++){
28             for(int j=i+1;j<k;j++){
29                 tmp=dis[i][j]+map[i][k]+map[k][j];
30                 if(tmp<minc){
31                     minc=tmp;
32                     num=0;
33                     p=j;
34                     while(p!=i){
35                         path[num++]=p;
36                         p=fa[i][p];
37                     }
38                     path[num++]=i;
39                     path[num++]=k;
40                 }
41             }
42         }
43         for(int i=1;i<=n;i++){
44             for(int j=1;j<=n;j++){
45                 if(dis[i][k]+dis[k][j]<dis[i][j]){
46                     dis[i][j]=dis[i][k]+dis[k][j];
47                     fa[i][j]=fa[k][j];     //记示i到j路径上j的前一个顶点,如：此处若在原图的基础上，j的前一个点为k ，即i->m>...->k->n->j则此处记录应为n。回溯时，把j换成n则f[i][n]=k
48                 }
49             }
50         }
51     }
52 }
53 
54 int main(){
55     int u,v,d;
56     while(scanf("%d%d",&n,&m)!=EOF){
57         init();
58         for(int i=1;i<=m;i++){
59             scanf("%d%d%d",&u,&v,&d);
60             if(map[u][v]>d)
61             map[u][v]=map[v][u]=dis[v][u]=dis[u][v]=d;
62         }
63         floyd();
64         if(minc==inf){
65             printf("No solution.
");
66         }
67         else{
68             while(num>0){
69                 printf("%d",path[--num]);
70                 if(num>0)
71                 printf(" ");
72             }
73             printf("
");
74           }
75     }
76     return 0;
77 }