无向图中的最小环问题

在一个给定的无向图中，任务是找出一个至少包含三个节点的环，要求环上的节点互不相同，并且环上所有边的总长度最小。这个问题被称为无向图的最小环问题。

你的任务是输出最小环的一个具体方案。如果有多个最小环，输出其中任意一个即可。

输入格式

第一行包含两个整数 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

解决方案代码示例

#include
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int g[N][N], dist[N][N];
int pos[N][N];
vector path;
int n, m;

// 获取路径
void get_path(int x, int y) {
int mid = pos[x][y];
if (mid == 0) return;
get_path(x, mid);
path.push_back(mid);
get_path(mid, y);
}

int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof(g));
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);
}
memcpy(dist, g, sizeof(dist));
int res = 0x3f3f3f3f;
for (int k = 1; k <= n; k++) {
for (int i = 1; i for (int j = i + 1; j if (dist[i][j] != INF && g[i][k] != INF && g[k][j] != INF) { // 防止三个 INF 相加导致溢出
if (dist[i][j] + g[i][k] + g[k][j] res = dist[i][j] + g[i][k] + g[k][j];
path.clear();
path.push_back(k);
path.push_back(i);
get_path(i, j);
path.push_back(j);
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
pos[i][j] = k;
}
}
}
}
if (res == 0x3f3f3f3f) cout <<"No solution." < else {
for (int i = 0; i cout < }
}
return 0;
}