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:

Note:

N will be in the range [1, 100].

K will be in the range [1, N].

The length of times will be in the range [1, 6000].

All edges 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.

743. Network Delay Time