Network Delay Time

The key idea

The time for all nodes to receive the signal equals the LONGEST of the shortest-path distances from the source to every node. Run Dijkstra from k; the answer is the maximum finalized distance, or -1 if any node stays unreachable.

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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 minimum 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.

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u_i, v_i <= n
u_i != v_i
0 <= w_i <= 100
All the pairs (u_i, v_i) are unique (no multiple edges).

Examples

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

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

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

Complexity

Time: O(E log V) Space: O(V + E)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →