题目描述
求节点1到其余所有点最短路的最大值,跟acwing1128一样,可以用floyd算法
C++ 代码
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int N, int t) {
vector<vector<int>> dist(N + 1, vector<int> (N + 1, 0x3f3f3f3f));
for (int i = 0; i < times.size(); i ++)
{
int a = times[i][0], b = times[i][1], c = times[i][2];
dist[a][b] = c;
}
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 (i != t)
res = max(res, dist[t][i]);
}
if (res == 0x3f3f3f3f)
{
return -1;
}
return res;
}
};