AcWing 344. 观光之旅题解（floyd求无向图的最小环问题）

AcWing 344. 观光之旅
这题是利用floyd的性质求无向图的最小环问题，注意记录路径和求最小中间点的先后顺序和顺序的意义（因为要求的是环，先求环的时候，此时k还未更新成i、j之间最短的点，所以在path[cnt ++ ] = k和下一行的get_min中path[cnt ++ ] = k的k值不同，保证了是一个环）

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], w[N][N];  //d储存最短路径，w储存边权值
int path[N];
int pos[N][N];
int cnt;

void get_path(int i, int j){
    
	if(pos[i][j] == 0) return ;
	
	int k = pos[i][j];
	get_path(i, k);  //找到i和中间点k之间经过的点并存入path数组中 
	path[cnt ++ ] = k;
	get_path(k, j);  //找到k和j之间经过的点并存入path数组中 
}

signed main()
{
    
	cin>>n>>m;
	memset(w, 0x3f, sizeof w);
	for(int i = 1; i <= n; i ++ ) w[i][i] = 0;
	
	while(m -- ){
    
		int a, b, c;
		cin>>a>>b>>c;
		w[a][b] = w[b][a] = min(w[a][b], c);
	}
	
	int res = INF;
	memcpy(d, w, sizeof d);
	
	for(int k = 1; k <= n; k ++ ){
    
		
		//这里比较疑惑的是为什么先求路径，再找两点之间最短距离
		//原因是，此时k还未更新成i、j之间最短的点
		//所以在path[cnt ++ ] = k和下一行的get_min中path[cnt ++ ] = k的k值不同，保证了是一个环
		//先求路径 
		for(int i = 1; i < k; i ++ ){
    
			for(int j = i + 1; j < k; j ++ ){
       if(res > (long long)d[i][j] + w[k][i] + w[j][k]){
      //找到更小环 
					res = d[i][j] + w[k][i] + w[j][k];  //注意按照环的方向 
					cnt = 0;  //重新记录路径 
					path[cnt ++ ] = k;  //这个环是从k出发
					path[cnt ++ ] = i;
					get_path(i, j);
					path[cnt ++ ] = j;					
				}
			} 
		}
		
		//求中间点
		for(int i = 1; i <= n; i ++ ){
    
			for(int j = 1; j <= n; j ++ ){
    
				if(d[i][j] > d[i][k] + d[k][j]){
    
					d[i][j] = d[i][k] + d[k][j];
					pos[i][j] = k;
				}
			}
		} 
	}
	
	if(res == INF) cout<<"No solution."<<endl;
	else{
    
		for(int i = 0; i < cnt; i ++ ) cout<<path[i]<<' ';
		cout<<endl; 
	}
	return 0;
}