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].
- 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.
来源: http://www.bubuko.com/infodetail-3400482.html