问题描述
m个点， m条边， 求图中存在的路径最小的环
样例
Sample Input
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
Sample Output
1 3 5 2
思路
用ans存最小环的距离，dis[i, j]存i 到 j 的最短路径， pass[i, j] 存 i 到 j 最短距离经过哪些点， path存最终的路径
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>using namespace std;const int N = 110;int g[N][N], dis[N][N], pass[N][N];
vector<int> path;
int n, m, ans = 0x3f3f3f3f;void get_path(int x, int y)
{if (pass[x][y] == 0)return;get_path(x, pass[x][y]);path.push_back(pass[x][y]);get_path(pass[x][y], y);
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);for (int i = 0; i <= n; i++)g[i][i] = 0;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(dis, g, sizeof g);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)dis[i][j] + g[i][k] + g[k][j] < ans){ans = dis[i][j] + g[i][k] + g[k][j];path.clear();path.push_back(i);get_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 (dis[i][j] > dis[i][k] + dis[k][j]){dis[i][j] = dis[i][k] + dis[k][j];pass[i][j] = k;}}if (ans == 0x3f3f3f3f){puts("No solution.");}else{for (int i = 0; i < path.size(); i++)cout << path[i] << " ";cout << endl;}return 0;
}