743. Network Delay Time
2021-04-22 10:27
标签：list cer class imp min solution end get belle There are Given Now, we send a signal from a certain node Example 1: Note: 1. floyd-warshall 初始化的时候i==j置0，表示没有走动 先把最终矩阵求出来，意思是从i到j的最短路径， 这道题最终转化成从节点k开始，最多要花多少步才能传播到所有节点，所以是上面的矩阵中取大值。 比如从2出发，到1要一步，到4要二步，答案就是2. 743. Network Delay Time 标签：list cer class imp min solution end get belle 原文地址：https://www.cnblogs.com/wentiliangkaihua/p/12244695.htmlN network nodes, labelled 1 to N.times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
N will be in the range [1, 100].K will be in the range [1, N].times will be in the range [1, 6000].times[i] = (u, v, w) will have 1 and
0 .class Solution {
public int networkDelayTime(int[][] times, int N, int K) {
double[][] disTo = new double[N][N];
for (int i = 0; i ) {
Arrays.fill(disTo[i], Double.POSITIVE_INFINITY);
}
for (int i = 0; i ) {
disTo[i][i] = 0;
}
for (int[] edge: times) {
disTo[edge[0] - 1][edge[1] - 1] = edge[2];
}
for (int k = 0; k ) {
for (int i = 0; i ) {
for (int j = 0; j ) {
if (disTo[i][j] > disTo[i][k] + disTo[k][j])
disTo[i][j] = disTo[i][k] + disTo[k][j];
}
}
}
double max = Double.MIN_VALUE;
for (int i = 0; i ) {
if (disTo[K - 1][i] == Double.POSITIVE_INFINITY) return -1;//如果有一个节点从k到不了，就说明无法完成任务返回-1
max = Math.max(max, disTo[K - 1][i]);
}
return (int) max;
}
}
