ACWing-344 观光之旅 题解

题目大意

给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。

你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

解题思路

模板题。。

比最小环模板多了一个记录路径的过程。

（没啥好说的，还是看代码吧。。

完整代码

#include <iostream>
using namespace std;

const int INF = 1e8;
int Map[200][200], dis[200][200],ne[200][200],n,path[200];
//ne[i][j]表示从i到j的经过的第一个节点

void Floyd() {
	int mins = INF,cnt;
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i < k; i++) {
			for (int j = i + 1; j < k; j++) {
				int tmp = dis[i][j] + Map[i][k] + Map[j][k];
				if (tmp < mins) {
					mins = tmp;
					cnt = 0;
					int p = i;
					while (p != j) {//输出从i到j的路径
						path[cnt++] = p;
						p = ne[p][j];
					}
					path[cnt++] = j;
					path[cnt++] = k;
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int tmp = dis[i][k] + dis[k][j];
				if (tmp < dis[i][j]) {
					dis[i][j] = tmp;
					ne[i][j] = ne[i][k];//记录路径
				}
			}
		}
	}
	if (mins == INF)	cout << "No solution." << endl;
	else {
		for (int i = 0; i < cnt; i++) {
			string s = i == cnt - 1 ? "\n" : " ";
			cout << path[i] << s;
		}
	}
}

int main() {
	int m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			Map[i][j] = dis[i][j] = INF,ne[i][j] = j;
		Map[i][i] = dis[i][i] = 0;
	}
	for (int i = 1; i <= m; i++) {
		int x, y, l;
		cin >> x >> y >> l;
		Map[x][y] = dis[x][y] = Map[y][x] = dis[y][x] = l;
	}
	Floyd();
}