月份：2019年7月

743. 网络延迟时间

有 N 个网络节点，标记为 1 到 N。

给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。

现在，我们向当前的节点 K 发送了一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。

注意:

N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

package gongel_first;

import java.util.Arrays;

public class Sevenhundred_fortyThree {
    /**
     * 还是考研时王道上学的Dijkstra
     */
    private int[] dist;
    //    private int[] path; 用于记录最短路径
    private boolean[] visited;

    private void dijkstra(int start, int[][] times, int N) {
        Arrays.fill(dist, 100000);
        int min, u = -1;
        dist[start] = 0;
//        for (int i = 1; i <= N; i++)
//            path[i] = i;
        for (int i = 1; i <= N; i++) {
            min = Integer.MAX_VALUE;
            for (int j = 1; j <= N; j++) {
                if (visited[j] == false && dist[j] < min) {
                    u = j;
                    min = dist[j];
                }
            }
            if (u == -1)
                continue;
            visited[u] = true;
            for (int k = 1; k <= N; k++) {
                if (visited[k] == false && dist[u] + times[u][k] < dist[k]) {
                    dist[k] = dist[u] + times[u][k];
//                    path[k] = u;
                }
            }
        }
    }

    public int networkDelayTime(int[][] times, int N, int K) {
        dist = new int[N + 1];
//        path = new int[N+1];
        visited = new boolean[N + 1];
        int[][] g = new int[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                g[i][j] = 100000;
            }
        }
        for (int[] t : times) {
            g[t[0]][t[1]] = t[2];
        }
        dijkstra(K, g, N);
        int max = -1;
        for (int i = 1; i <= N; i++)
            max = Math.max(max, dist[i]);
        if (max == 100000)
            return -1;
        return max;
    }
}

Dijkstra