743. Network Delay Time

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int MAX = Integer.MAX_VALUE / 2;

        int[][] grid = new int[n + 1][n + 1];
        for (int[] g : grid) {
            Arrays.fill(g, MAX);
        }
        for (int[] time : times) {
            grid[time[0]][time[1]] = time[2];
        }

        int[] distance = new int[n + 1]; // 与节点 k 的距离
        Arrays.fill(distance, MAX);
        distance[k] = 0;

        boolean[] used = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            int nearest = -1;
            for (int j = 1; j <= n; j++) {
                if (!used[j] && (nearest == -1 || distance[j] < distance[nearest])) {
                    nearest = j;
                }
            }

            // 使用找到的距离源点最近的点，遍历所有边，更新相邻节点与源点的距离
            for (int j = 1; j <= n; j++) {
                int dist = grid[nearest][j];
                distance[j] = Math.min(distance[j], distance[nearest] + dist);
            }
            used[nearest] = true;
        }

        int time = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            time = Math.max(time, distance[i]); // 注意次数是找最大值，因为如果无法通过 k 触达某节点，那么该节点的距离为最大值
        }
        return time == MAX ? -1 : time;
    }
}

References

743. Network Delay Time