AcWing 344. Solution to the problem of sightseeing tour (Floyd finding the minimum ring of undirected graph)

AcWing 344. Sightseeing tour
Use this question floyd To find the minimum ring problem of undirected graphs , Pay attention to the sequence and significance of recording the path and finding the minimum intermediate point （ Because what is required is a ring , When you first find the ring , here k Not updated to i、j The shortest point between , So in path[cnt ++ ] = k And the next line get_min in path[cnt ++ ] = k Of k Values are different , It is guaranteed to be a ring ）

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int d[N][N], w[N][N];  //d Store the shortest path ,w Store edge weights 
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);  // find i And the middle point k And save path Array  
	path[cnt ++ ] = k;
	get_path(k, j);  // find k and j And save path Array  
}

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 ++ ){
    
		
		// What is more puzzling here is why to seek the path first , Find the shortest distance between two points 
		// as a result of , here k Not updated to i、j The shortest point between 
		// So in path[cnt ++ ] = k And the next line get_min in path[cnt ++ ] = k Of k Values are different , It is guaranteed to be a ring 
		// Find the path first  
		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]){
      // Find a smaller ring  
					res = d[i][j] + w[k][i] + w[j][k];  // Pay attention to the direction of the ring  
					cnt = 0;  // Re record the path  
					path[cnt ++ ] = k;  // This ring is from k set out 
					path[cnt ++ ] = i;
					get_path(i, j);
					path[cnt ++ ] = j;					
				}
			} 
		}
		
		// Find the middle point 
		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;
}