题目描述
给定一张无向图，求图中一个至少包含 \(3\) 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.。
输入格式
第一行两个正整数 \(n,m\) 表示点数和边数。
接下来 \(m\) 行，每行三个正整数 \(u,v,d\)，表示节点 \(u,v\) 之间有一条长度为 \(d\) 的边。
输出格式
输出边权和最小的环的边权和。若无解，输出 No solution.。
输入输出样例 #1
输入 #1
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
输出 #1
61
说明/提示
样例解释：一种可行的方案：\(1-3-5-2-1\)。
对于 \(20\%\) 的数据，\(n,m \leq 10\)。
对于 \(60\%\) 的数据，\(m\leq 100\)。
对于 \(100\%\) 的数据，\(1\le n\leq 100\)，\(1\le m\leq 5\times 10^3\)，\(1 \leq d \leq 10^5\)。
无解输出包括句号。
#include <iostream>
#include <cstring>
using namespace std;const int maxn = 104;
const int INF = 0x3f3f3f3f;int n, m;
int e[maxn][maxn]; // 原始图的边权
int dist[maxn][maxn]; // 最短路径距离
int Ans;int main() {cin >> n >> m;memset(e, 0x3f, sizeof(e));memset(dist, 0x3f, sizeof(dist));for (int i = 1; i <= m; i++) {int x, y, z;cin >> x >> y >> z;e[x][y] = e[y][x] = z;dist[x][y] = dist[y][x] = z;}Ans = INF;// Floyd算法求最小环for (int k = 1; k <= n; k++) {// 检查经过k的环：i -> k -> j -> (通过1~k-1的最短路) -> ifor (int i = 1; i < n; i++) {for (int j = i + 1; j <= n; j++) {if (dist[i][j] != INF && e[j][k] != INF && e[k][i] != INF) {// 环长 = i到j的最短路 + i到k的边 + j到k的边Ans = min(Ans, dist[i][j] + e[k][i] + e[j][k]);}}}// 正常的Floyd更新for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}if (Ans == INF) {cout << "No solution." << endl;} else {cout << Ans << endl;}return 0;
}