解题思路

题目大意：给定一张无向图，求图中至少一个包含三个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。若无解，输出“$No solution.$”。图的节点数不超过$100$。

题目分析： 最小环的模板题，因为$floyd$实质上是阶段性$dp$，所以我们可以在每个阶段都判断一次，具体的判断方法是，最外层的$k$控制着编号的最大值，此时$d[i][j]$保存着“编号不超过$k-1$的节点”从$i$到$j$的最短路，所以每次我们可以让$k$作为一个基准点，然后里面两层的$i$和$j$代表着$k$左边和右边的点，判断一下能否连成环并且其环上的权值和小于当前最小值的条件是$d[i][j]+maze[j][k]+maze[k][i]$即作为当前$i->j->k->i$环上的权值，若其中只要有某一项的值为$inf$，则此环不连通，换句话说这就不是一个环了， 只要能连成环的话我们就可以更新答案，至于怎么找环上的点，我们只需要在$floyd$更新答案的时候顺便记录一下中间点即可，$pos[x][y]=k$，代表的就是$x$和$y$点是由中间点$k$拼接而成的，然后用一个递归就能直接按顺序求出环上的节点了。

这里有个坑需要注意一下，$d[i][j]+maze[j][k]+maze[k][i]$这里记得开$longlong$运算，因为假如三个值都为$inf$，相加就爆掉$int$了，所以我们需要用$longlong$过度一下，然后就没了。

标程

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
  
typedef long long LL;
  
const int inf=0x3f3f3f3f;
 
const int N=110;
 
int maze[N][N],d[N][N],pos[N][N];//pos[x][y]:点x和点y的中间点
 
vector<int>path;
 
void find_path(int x,int y)
{
	if(pos[x][y]==0)
		return;
	find_path(x,pos[x][y]);
	path.push_back(pos[x][y]);
	find_path(pos[x][y],y);
} 
 
int main()
{
//  freopen("input.txt","r",stdin);
//	ios::sync_with_stdio(false);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			d[i][j]=maze[i][j]=i==j?0:inf;
	while(m--)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		d[u][v]=d[v][u]=maze[u][v]=maze[v][u]=min(maze[u][v],w);
	}
	int ans=inf;
	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]+maze[j][k]+maze[k][i]<ans)//i->j->k->i的一个环
				{
					ans=d[i][j]+maze[j][k]+maze[k][i];
					path.clear();
					path.push_back(i);
					find_path(i,j);
					path.push_back(j);
					path.push_back(k);
				} 
		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;//表示k当了点i和j的中间点才能缩短路径 
				}
	}
	if(ans==inf)
		printf("No solution.\n");
	else
	{
		for(int i=0;i<path.size();i++)
			printf("%d ",path[i]);
	}
    return 0;
}