There are N network nodes, labelled 1 to N.
Given 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.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2
Note:
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 <= u, v <= N and 0 <= w <= 100.class Solution { public int networkDelayTime(int[][] times, int N, int K) { double[][] disTo = new double[N][N]; for (int i = 0; i < N; i++) { Arrays.fill(disTo[i], Double.POSITIVE_INFINITY); } for (int i = 0; i < N; i++) { disTo[i][i] = 0; } for (int[] edge: times) { disTo[edge[0] - 1][edge[1] - 1] = edge[2]; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; 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 < N; i++) { if (disTo[K - 1][i] == Double.POSITIVE_INFINITY) return -1;//如果有一个节点从k到不了，就说明无法完成任务返回-1 max = Math.max(max, disTo[K - 1][i]); } return (int) max; } }
1. floyd-warshall
初始化的时候i==j置0，表示没有走动
先把最终矩阵求出来，意思是从i到j的最短路径，
这道题最终转化成从节点k开始，最多要花多少步才能传播到所有节点，所以是上面的矩阵中取大值。
比如从2出发，到1要一步，到4要二步，答案就是2.
原文：https://www.cnblogs.com/wentiliangkaihua/p/12244695.html