URAL 1004 Sightseeing Trip（floyd求最小环+路径输出）

题意：
求路径最小的环（至少三个点），并且输出路径。

思路：

一开始INF开大了...无限wa，原来相加时会爆int...

路径输出的算法是这样的：

接下来就要看一看如何找出最短路径所行经的城市了，这里要用到另一个矩阵P，它的定义是这样的：p(ij)的值如果为p，就表示i到j的最短行经为i->...->p->j，也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i->...->p->j；再去找p(ip)，如果值为q，i到p的最短路径为i->...->q->p；再去找p(iq)，如果值为r，i到q的最短路径为i->...->r->q；所以一再反复，到了某个p(it)的值为i时，就表示i到t的最短路径为i->t，就会的到答案了，i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。
但是，如何动态的回填P矩阵的值呢？回想一下，当d(ij)>d(ik)+d(kj)时，就要让i到j的最短路径改为走i->...->k->...->j这一条路，但是d(kj)的值是已知的，换句话说，就是k->...->j这条路是已知的，所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的，当然，因为要改走i->...->k->...->j这一条路，j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj)，就把p(kj)存入p(ij)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 const int INF = 1<<28;
 7 const int maxn = 100+10;
 8 
 9 int n,m;
10 int ans,num;
11 int g[maxn][maxn],dis[maxn][maxn];
12 int path[maxn],pre[maxn][maxn];
13 
14 void floyd()
15 {
16     for(int k=1;k<=n;k++)
17     {
18         for(int i=1;i<k;i++)
19         for(int j=i+1;j<k;j++)
20         {
21             int tmp = dis[i][j]+g[i][k]+g[k][j];  //从k点出发，回到k点
22             if(tmp<ans)
23             {
24                 ans = tmp;
25                 num = 0;
26                 int p = j;
27                 while(p!=i)
28                 {
29                     path[num++] = p; //记录路径
30                     p = pre[i][p];
31                 }
32                 path[num++] = i;
33                 path[num++] = k;
34             }
35         }
36         for(int i=1;i<=n;i++)
37         for(int j=1;j<=n;j++)
38         {
39             if(dis[i][j]>dis[i][k]+dis[k][j])
40             {
41                 dis[i][j] = dis[i][k] + dis[k][j];
42                 pre[i][j] = pre[k][j];
43             }
44         }
45     }
46 }
47 
48 
49 int main()
50 {
51    //freopen("in.txt","r",stdin);
52     while(scanf("%d",&n) , n!=-1)
53     {
54         scanf("%d",&m);
55         for(int i=1;i<=n;i++)
56         for(int j=1;j<=n;j++)
57         {
58             if(i==j)  g[i][j]=dis[i][j]=0;
59             else g[i][j]=dis[i][j]=INF;
60             pre[i][j] = i;
61         }
62         for(int i=0;i<m;i++)
63         {
64             int u,v,w;
65             scanf("%d%d%d",&u,&v,&w);
66             if(dis[u][v]>w)
67             {
68                 g[u][v]=g[v][u]=dis[u][v]=dis[v][u]=w;
69             }
70         }
71         ans = INF;
72         floyd();
73         if(ans==INF)  printf("No solution.
");
74         else
75         {
76             for(int i=0;i<num;i++)  printf("%d%c",path[i],i==num-1?'
':' ');
77         }
78     }
79     return 0;
80 }