Network Signal Delay
A network has n nodes labelled 1 to n. Each entry [u, v, w] in times is a one-way link: a signal sent from u reaches v after w milliseconds.
A signal is broadcast from node k. Return the time it takes for every node to receive it, which is the largest shortest-path distance from k. If some node can never be reached, return -1.
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 = 2 Output: -1 Explanation: Node 1 cannot be reached from node 2.
Constraints
- 1 <= n <= 100
- 0 <= times.length <= 6000
- 0 <= w <= 100
- 1 <= k <= n
Hint 1
All weights are non-negative, so Dijkstra with a min-heap gives the shortest arrival time at every node.
Hint 2
The answer is the maximum of those times, or -1 if any node stays unreached.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Site Reliability Engineer, Cloud Engineer, DevOps Engineer, Embedded Systems Engineer, Blockchain Developer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.