https://vjudge.net/problem/URAL-1004
题意：
求路径最小的环（至少三个点），并且输出路径。
思路：
一开始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)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF = <<;
const int maxn = +; int n,m;
int ans,num;
int g[maxn][maxn],dis[maxn][maxn];
int path[maxn],pre[maxn][maxn]; void floyd()
{
for(int k=;k<=n;k++)
{
for(int i=;i<k;i++)
for(int j=i+;j<k;j++)
{
int tmp = dis[i][j]+g[i][k]+g[k][j]; //从k点出发，回到k点
if(tmp<ans)
{
ans = tmp;
num = ;
int p = j;
while(p!=i)
{
path[num++] = p; //记录路径
p = pre[i][p];
}
path[num++] = i;
path[num++] = k;
}
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
{
dis[i][j] = dis[i][k] + dis[k][j];
pre[i][j] = pre[k][j];
}
}
}
} int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d",&n) , n!=-)
{
scanf("%d",&m);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(i==j) g[i][j]=dis[i][j]=;
else g[i][j]=dis[i][j]=INF;
pre[i][j] = i;
}
for(int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if(dis[u][v]>w)
{
g[u][v]=g[v][u]=dis[u][v]=dis[v][u]=w;
}
}
ans = INF;
floyd();
if(ans==INF) printf("No solution.\n");
else
{
for(int i=;i<num;i++) printf("%d%c",path[i],i==num-?'\n':' ');
}
}
return ;
}