Advanced Graphs Weighted shortest paths
471. Network Delay Time
A network has n nodes, labelled from 1 to n. You are given a list times of one-way links, where
times[i] = [u, v, w] means that a signal sent from node u reaches node v after w units of time.
At time 0, node k sends out a signal. Every node that receives the signal passes it on along all of its
outgoing links at once. Return the time at which the last node receives the signal. If some node never
receives it, return -1.
A node receives the signal at the earliest time that any chain of links from k brings it there.
Example 1
Input: times = [[1, 2, 4],
[1, 3, 1],
[3, 2, 2],
[2, 4, 1],
[3, 4, 6]]
n = 4
k = 1
4Explanation: Node 3 receives the signal at time 1. Node 2 receives it at time 3 through node 3, before the direct link would bring it at time 4. Node 4 receives it last, at 3 + 1 = 4.
Example 2
Input: times = [[1, 2, 7], [3, 2, 1]], n = 3, k = 1
-1Explanation: The link between nodes 3 and 2 only goes from 3 to 2, so the signal from node 1 never reaches node 3.
Example 3
Input: times = [[1, 2, 1000000000],
[2, 3, 1000000000],
[3, 4, 1000000000]]
n = 4
k = 1
3000000000Explanation: The signal crosses three links of 109 each, so node 4 receives it at 3 × 109.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ n ≤ 1050 ≤ times.length ≤ 105times[i] = [u, v, w], with1 ≤ u, v ≤ nand0 ≤ w ≤ 1091 ≤ k ≤ n- Two links can join the same two nodes, and a link can lead from a node back to itself.
Clarifying questions
What you would ask an interviewer before writing any code.