LeetCode [743] Network Delay Time

 743. Network Delay Time

Medium

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:

1. N will be in the range [1, 100].
2. K will be in the range [1, N].
3. The length of times will be in the range [1, 6000].
4. All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public int networkDelayTime(int[][] times, int N, int K) { int w = Integer.MIN_VALUE; int[] dist = new int[N+1]; Arrays.fill(dist, Integer.MAX_VALUE); dist[K] = 0; for(int i=0; i<N; ++i){ for(int[] e : times){ int u = e[0], v = e[1], t = e[2]; if(dist[u]!=Integer.MAX_VALUE && dist[u]+t<dist[v]){ dist[v] = dist[u]+t; } } } for(int i=1; i<=N; ++i){ w = Math.max(w, dist[i]); } return w==Integer.MAX_VALUE?-1:w; } }