AcWing 1128. 信使
原题链接
简单
作者:
sailor
,
2022-02-25 09:34:06
,
所有人可见
,
阅读 158
/*
题意总结:
不能用BFS,因为BFS要求所以边的权重一样。真的像计网里边Dijkstra那里的泛洪算法
就是求出来所有点到起点的距离,然后这些距离的最大值就是答案。
由于数据范围很小,所以直接使用多源最短路的floyd就可以。
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N];
int main()
{
cin >> n >> m;
// 初始化,使用邻接矩阵记得初始化对角线。
memset(d, 0x3f, sizeof d);
for(int i=1; i<=n; i++) d[i][i] = 0;
for(int i = 0; i<m; i++)
{
int a, b , c;
cin >> a >> b >> c;
// 没说不存在重边,所以有可能存在重边
d[a][b] = d[b][a] = min(d[a][b], c);
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
int res = 0;
for(int i=1; i<=n; i++)
if(d[1][i] == INF)
{
res = -1;
break;
}
else res = max(res, d[1][i]);
cout<<res <<endl;
return 0;
}
tql