67 lines
2.3 KiB
C++
67 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110, INF = 0x3f3f3f3f;
|
||
int n, m;
|
||
int g[N][N], dis[N][N];
|
||
vector<int> path;
|
||
int mid[N][N];
|
||
int ans = INF;
|
||
|
||
// i->j之间的最短路径中途经点有哪些
|
||
void get_path(int i, int j) {
|
||
int k = mid[i][j]; // 获取中间转移点
|
||
if (!k) return; // 如果i,j之间没有中间点，停止
|
||
get_path(i, k); // 递归前半段
|
||
path.push_back(k); // 记录k节点
|
||
get_path(k, j); // 递归后半段
|
||
}
|
||
|
||
int main() {
|
||
// n个顶点，m条边
|
||
cin >> n >> m;
|
||
|
||
// 初始化邻接矩阵
|
||
memset(g, 0x3f, sizeof g);
|
||
for (int i = 1; i <= n; i++) g[i][i] = 0; // 邻接矩阵，自己到自己距离是0
|
||
|
||
while (m--) {
|
||
int a, b, c;
|
||
cin >> a >> b >> c;
|
||
g[a][b] = g[b][a] = min(g[a][b], c); // 求最短路之类，(a,b)之间多条边输入只保留最短边
|
||
}
|
||
|
||
// 把原始地图复制出来到生成最短距离dis
|
||
memcpy(dis, g, sizeof dis);
|
||
|
||
for (int k = 1; k <= n; k++) {
|
||
// DP
|
||
for (int i = 1; i < k; i++)
|
||
for (int j = i + 1; j < k; j++)
|
||
if (g[i][k] + g[k][j] < ans - dis[i][j]) { // 减法防止爆INT
|
||
ans = dis[i][j] + g[i][k] + g[k][j];
|
||
// 包含最小环的所有节点（按顺序输出）
|
||
// 找到长度更小的环，需要记录路径,并且要求: 最小环的所有节点（按顺序输出）
|
||
path.clear(); // 每次找到新的最小环,那path就是为最小的环而准备的，以前的都作废掉
|
||
path.push_back(i); // 序号：i < j < k
|
||
get_path(i, j);
|
||
path.push_back(j);
|
||
path.push_back(k);
|
||
}
|
||
|
||
// 正常floyd
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
if (dis[i][j] > dis[i][k] + dis[k][j]) {
|
||
dis[i][j] = dis[i][k] + dis[k][j];
|
||
mid[i][j] = k; // 记录路径i->j 是通过k进行转移的
|
||
}
|
||
}
|
||
|
||
if (ans == INF)
|
||
puts("No solution.");
|
||
else
|
||
for (int i = 0; i < path.size(); i++) cout << path[i] << ' ';
|
||
|
||
return 0;
|
||
} |