C++ 代码
/*
将所有环按照环中最大的点的编号分类1,2,3,...,n-1,n
floyd求最小环:
for(int k=1;k<=n;k++)
//在这个位置的d[i][j](i<k,j<k)正好是i,j之间经历过[1,k-1]之间的点,[1,k]的情况还没被更新
//所以当前第k类环的权值为-->d[i][j]+w[i][k]+w[k][j]
//每次用它更新最终结果res即可
//如果res被更新path[cnt++]=i;//最终路径k->i->...->j
//get_path(i,j);
//path[cnt++]=j;
for(int i=1;;i<=n;i++)
for(int j=1;j<=n;j++)
//正常floyd求两点之间最短距离
if(d[i][j]>d[i][k]+d[k][j])
d[i][j]=d[i][k]+d[k][j]
pos[i][j]=k;//记录i->j是从k点转移过来的
void get_path(i,j)函数,输出所有的在i->j最短路径上的点
{
int k=pos[i][j];
get_path(i,k);
path[cnt++]=k;
get_path(k,j);
}
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int d[N][N],g[N][N];
int pos[N][N];
int path[N],cnt;
int n,m;
void get_path(int i,int j)
{
if(pos[i][j]==0) return;
int k=pos[i][j];
get_path(i,k);
path[cnt++]=k;
get_path(k,j);
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++) g[i][i]=0;
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
int res=INF;//存最小环
memcpy(d,g,sizeof d);
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if((long long)d[i][j]+g[i][k]+g[k][j]<res)
{
res=d[i][j]+g[i][k]+g[k][j];
cnt=0;//重新写最终路径
path[cnt++]=k;
path[cnt++]=i;
get_path(i,j);
path[cnt++]=j;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(d[i][j]>d[i][k]+d[k][j])
{
d[i][j]=d[i][k]+d[k][j];
pos[i][j]=k;
}
}
}
}
if(res==INF) puts("No solution.");
else
{
for(int i=0;i<cnt;i++) cout<<path[i]<<" ";
}
return 0;
}