AcWing 1128. Messenger solution (shortest path Floyd)

AcWing 1128. messenger
floyd Find the shortest path , Triple cycle , Let every point try to act as the middle point to find the shortest path , Remember to initialize the self ring . Broadcast model , Is to find the maximum value of all the shortest paths ,

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int dist[N][N];
int n, m;

int main()
{
    
	cin>>n>>m;
	memset(dist, 0x3f, sizeof dist);
	for(int i = 0; i <= n; i ++ ) dist[i][i] = 0;  // Remember to initialize the self ring  
	for(int i = 0; i < m; i ++ ){
    
		int a, b, c;
		cin>>a>>b>>c;
		dist[a][b] = dist[b][a] = min(c, dist[a][b]); 
	}
	
	//floyd Every point is regarded as the middle point to try to find the shortest path , So the middle point circulates in the outermost layer  
	for(int k = 1; k <= n; k ++ ){
    
		for(int i = 1; i <= n; i ++ ){
    
			for(int j = 1; j <= n; j ++ ){
    
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 
			}
		}
	}
	
	int res = 0;
	for(int i = 1; i <= n; i ++ ){
    
		if(dist[1][i] == INF){
    
			res = -1;
			break;
		}
		res = max(res, dist[1][i]);
	}
	cout<<res<<endl;
	return 0;
}