Network Delay Time

Medium · Advanced Graphs

You are given a list of directed wires connecting nodes in a network, each described as [source, target, travel_time]. There are n nodes labeled from 1 to n, and a signal starts at node k. Return the minimum time needed for the signal to reach every node in the network. If some node can never be reached, return -1.

Examples

Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Why:    From node 2 it takes 1 step to reach nodes 1 and 3, and 2 steps to reach node 4, so the last node receives the signal at time 2.

Input:  times = [[1,2,1]], n = 2, k = 1
Output: 1
Why:    Node 2 receives the signal after 1 unit of time and there are no other nodes to reach.

Input:  times = [[1,2,1]], n = 2, k = 2
Output: -1
Why:    There is no path from node 2 to node 1, so node 1 never receives the signal.

Constraints

1 <= n <= 100, 1 <= times.length <= 6000, times[i] = [u, v, w] with 1 <= u, v <= n, u != v, 0 <= w <= 100, 1 <= k <= n

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Network Delay Time

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Network Delay Time. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.