poj 1734 Sightseeing trip 求最小代价环

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 const int MAX=1234567;
 6 #define N 110
 7 int g[N][N];
 8 int dis[N][N];
 9 int ans[N];
10 int p[N][N];//记录i——j之间的路径//记录前驱
11 int n,m;
12 int minm;
13 int cnt;
14 int mid;
15 void floyd(){
16     int i,j,k;
17     for(k=1;k<=n;k++){
18         //求环
19         for(i=1;i<k;i++){ //这里的结束条件是为了不出现重复
20             for(j=1;j<i;j++){
21                 if(dis[i][j]+g[i][k]+g[j][k]<minm){
22                     minm = dis[i][j]+g[i][k]+g[j][k];
23                     cnt = 0;
24                     mid = j;
25                     while(mid != i){
26                         ans[cnt++] = mid;
27                         mid = p[i][mid];//由i到当前点的前驱
28                     }
29                     ans[cnt++] = i;
30                     ans[cnt++] = k;
31                 }
32             }
33         }
34         //求最短路
35         for(i=1;i<=n;i++){
36             for(j=1;j<=n;j++){
37                 if(dis[i][k]+dis[k][j]<dis[i][j]){
38                     dis[i][j] = dis[i][k]+dis[k][j];
39                     p[i][j] = p[k][j]; //更新前驱
40                 }
41             }
42         }
43     }
44 }
45 
46 int main(){
47     while(scanf("%d%d",&n,&m) != -1){
48         int i,j;
49         for(i=1;i<=n;i++){
50             for(j=1;j<=n;j++){
51                 g[i][j] = MAX;
52                 dis[i][j] = MAX;
53                 p[i][j] = i;  //记录由i到j的前驱为i
54             }
55             g[i][i] = dis[i][i] = 0;
56         }
57         while(m--){
58             int a,b,c;
59             scanf("%d%d%d",&a,&b,&c);
60             if(c < g[a][b]){
61                 g[a][b] = g[b][a] = c;
62                 dis[a][b] = dis[b][a] = c;
63             }
64         }
65         minm = MAX;
66         floyd();
67         if(minm == MAX)puts("No solution.");
68         else {
69             printf("%d",ans[0]);
70             for(i=1;i<cnt;i++)
71             printf(" %d",ans[i]);
72             printf("\n");
73         }
74     }
75     return 0;
76 }