1. 问题描述：

给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式

第一行包含两个整数 N 和 M，表示无向图有 N 个点，M 条边。接下来 M 行，每行包含三个整数 u，v，l，表示点 u 和点 v 之间有一条边，边长为 l。

输出格式

输出占一行，包含最小环的所有节点（按顺序输出），如果不存在则输出 No solution.。

数据范围

1 ≤ N ≤ 100，
1 ≤ M ≤ 10000，
1 ≤ l < 500

输入样例：

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出样例：

1 3 5 2
来源：https://www.acwing.com/problem/content/description/346/

2. 思路分析：

3. 代码如下：

from typing import Listclass Solution:# 使用一个全局变量来记录当前环中的对应位置count = 0def getPath(self, i: int, j: int, path: List[int], pos: List[List[int]]):if pos[i][j] == 0: returnk = pos[i][j]# 类似于中序遍历的顺序可以使得得到的环的编号是按顺序的self.getPath(i, k, path, pos)path[self.count] = kself.count += 1self.getPath(k, j, path, pos)def floyd(self, n: int, g: List[List[int]], dis: List[List[int]]):res = 10 ** 10path = [0] * n# pos记录两点之间的最短距离是由哪一个点转移得到的pos = [[0] * (n + 1) for i in range(n + 1)]for k in range(1, n + 1):# 在floyd算法求解的过程中当前其实得到的是1~k-1编号的任意两点之间的最短路径for i in range(1, k):for j in range(i + 1, k):if dis[i][j] + g[j][k] + g[k][i] < res:# 注意需要环是按顺序的res = dis[i][j] + g[i][k] + g[k][j]self.count = 0self.getPath(i, j, path, pos)path[self.count] = jself.count += 1path[self.count] = kself.count += 1path[self.count] = iself.count += 1for i in range(1, n + 1):for j in range(1, n + 1):if dis[i][j] > dis[i][k] + dis[k][j]:dis[i][j] = dis[i][k] + dis[k][j]# pos记录的k是最小的kpos[i][j] = kINF = 10 ** 10if res == INF: print("No solution.")else:for i in range(self.count): print(path[i], end=" ")def process(self):n, m = map(int, input().split())INF = 10 ** 10# 使用邻接表存储会比较方便一点g = [[INF] * (n + 1) for i in range(n + 1)]for i in range(1, n + 1):# 自己到自己的点距离为0g[i][i] = 0for i in range(m):x, y, z = map(int, input().split())g[x][y] = g[y][x] = min(g[x][y], z)# 拷贝二维列表到dis中dis = [x[:] for x in g]self.floyd(n, g, dis)if __name__ == "__main__":Solution().process()