AcWing 1128. 信使 题解（最短路—Floyd）

AcWing 1128. 信使
floyd求最短路，三重循环，让每一个点都试着担任中间点去去找最短路，记得初始化自环。广播模型，就是找到所有最短路中最大值，

#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;  //记得初始化自环 
	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是以每一个点都当成中间点尝试找到最短路，所以中间点在最外层循环 
	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;
}