观光之旅

// 观光之旅.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
* https://www.acwing.com/problem/content/description/346/
* 
* 
给定一张无向图，求图中一个至少包含 3 个点的环，环上的节点不重复，并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。

输入格式
第一行包含两个整数 N 和 M，表示无向图有 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


3 2
1 2 6
3 1 3

*/




#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using  namespace std;

typedef long long LL;
const int N = 105;
int d[N][N]; int g[N][N];
int pos[N][N];
int n, m;
vector<int> anspath;


void getpath(int a, int b) {
	if (pos[a][b] == 0) return;
	int k = pos[a][b];
	getpath(a, k);
	anspath.push_back(k);
	getpath(k,b);
}


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] = min(g[a][b], c);
		g[b][a] = min(g[b][a], c);
	}

	memcpy(d, g, sizeof g);

	int ans = 0x3f3f3f3f;
	for (int k = 1; k <= n; k++) {

		for (int i = 1; i < k; i++) {
			for (int j = i+1; j < k; j++) {
				if ((LL)d[i][k] + d[k][j] + g[i][j] < ans) {
					ans = d[i][k] + d[k][j] + g[i][j];
					anspath.clear();
					anspath.push_back(k);
					anspath.push_back(i);
					getpath(i,j);
					anspath.push_back(j);
				}
			}
		}


		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (g[i][j] > g[i][k] + g[k][j]) {
					g[i][j] = g[i][k] + g[k][j];
					pos[i][j] = k;
				}
			}
		}
	}

	if (ans == 0x3f3f3f3f) {
		cout << "No solution." << endl;
	}
	else {
		for (int i = 0; i < anspath.size(); i++) {
			cout << anspath[i] << " ";
		}
		cout << endl;
	}

	return 0;
}