https://leetcode-cn.com/problems/network-delay-time/

problem

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

example

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

solution

/**
source k , target 1...k-1 k+1..n
dist[i] present time cost (the shortest path) from k to i
 (use  dijkstra algorithm)
result is  Math.max(dist[i])
 */
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
          final int INF = Integer.MAX_VALUE / 2;
        int[][] g = new int[n][n];
        for (int i = 0 ; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = INF;
            }
        }
        for(int[] t: times) {
            int u = t[0] -1;
            int v = t[1] -1;
            g[u][v] = t[2];
        }
        int[] dist = new int[n];
        Arrays.fill(dist,  INF);
        dist[k-1] = 0;
        boolean[] used = new boolean[n];
        for (int i = 0; i < n; ++i) {
            int x = -1;
            for (int y = 0; y < n; y++) {
                if ((!used[y] )&&( x == -1 || dist[y] < dist[x] )) {
                    x = y;
                }
            }
            used[x] = true;
            for (int y = 0 ; y < n; y++) {
                dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
            }
        }
       int ans = Arrays.stream(dist).max().getAsInt();
        return ans == INF ? -1 : ans;

     }
}