思路 : Floyd 实质 dp ,优化掉了第三维. dp [ i ] [ j ] [ k ] 指的是前k个点优化后 i -> j 的最短路。
所以我们就可以利用这个性质去求 最小环，最小环的构成可以看作是由一条 i -> k k->j 加上 dp [ i ] [ j ]的最短路
那么我们可以利用 还没有用 k 优化的 i - >j 的最短路 去求，这样保证了 ，这是一个真正的环。
#include<stdio.h>
#include<iostream>
using namespace std;
#define maxn 123
#define inf 1e8
int dis[maxn][maxn],n,key;
int gra[maxn][maxn],m,id;
int u,v,w,pre[maxn][maxn],ans[maxn];
void floyd()
{
key=inf;
for(int k=1; k<=n; k++)
{
for(int i=1; i<k; i++)
{
for(int j=i+1; j<k; j++)
{
int tmp=dis[i][j]+gra[i][k]+gra[k][j];
if(tmp<key)
{
key=tmp;
id=0;
int p=j;
while(p!=i)
{
ans[id++]=p;
p=pre[i][p];
}
ans[id++]=i;
ans[id++]=k;
}
}
}
for(int i=1; i<=n; i++)
for(int j=1; 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()
{
while(~scanf("%d%d",&n,&m))
{
key=inf;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
gra[i][j]=dis[i][j]=inf;
pre[i][j]=i;
}
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&u,&v,&w);
gra[u][v]=gra[v][u]=dis[u][v]=dis[v][u]=min(gra[u][v],w);
}
floyd();
if(key==inf)printf("No solution.\n");
else
{
printf("%d",ans[0]);
for(int i=1; i<id; i++)
printf(" %d",ans[i]);
printf("\n");
}
}
return 0;
}