noodleProblems/
Network Delay Time
#151

Network Delay Time

AlgorithmmediumDepth First SearchBreadth First SearchGraphHeap Priority Queue

You have a network of n nodes labelled 1 to n. You are given times, a list of directed travel times times[i] = [u, v, w] meaning a signal takes w time to travel from node u to node v.

A signal is sent from node k. Return the **minimum time** for *all* n nodes to receive the signal. If it is impossible for every node to receive it, return -1.

The time for all nodes to receive the signal is the *latest* of the shortest arrival times — the signal reaches each node along its fastest route, and you wait for the slowest of those.

Example cases

  • signal reaches all four
    in times =
    211
    231
    341
    n = 4k = 2
    out 2
    From node 2: node 1 arrives at t=1, node 3 at t=1, node 4 at t=2. The slowest is 2.
  • single node
    in times = [], n = 1, k = 1
    out 0
    The source is the only node and already has the signal — zero time.
  • node unreachable
    in times =
    121
    n = 2k = 2
    out -1
    Starting at node 2, there is no edge out of 2, so node 1 never receives the signal.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= u, v <= n
  • u != v
  • 0 <= w <= 100
  • All pairs (u, v) are unique (no duplicate edges).
Saved
times =
[[2,1,1],[2,3,1],[3,4,1]]
n =
4
k =
2