Show problems as
Classic problem #743MediumDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest PathDijkstra's Algorithm

Network Delay Time

Real-world version: Relay Broadcast Time
Tracked in this browser only
Read Network Delay Time on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstWith Graphs · Priority Queues, animated step by step

A courier firm runs depots sorting depots numbered 1 through depots. Its one-way shuttle legs are listed in legs, where legs[i] = [u_i, v_i, w_i] means a shuttle leaves depot u_i for depot v_i and the crossing takes w_i minutes. A leg is usable in that direction only. No two legs share the same ordered pair of depots.

At minute 0 a dispatch note is posted at depot origin. A depot forwards a copy of the note along every leg leaving it the instant the note arrives, and copies travel at the same time without interfering. A depot counts as served the first moment any copy reaches it, and the origin is served at minute 0. Some legs take 0 minutes.

Return the minute at which the last depot is served. If at least one depot is never served, return -1.

Examples

Example 1

Input
legs = [[1,2,3],[2,3,4],[1,3,9]], depots = 3, origin = 1
Output
7

Depot 1 holds the note at minute 0, depot 2 is served at minute 3, and a copy forwarded from depot 2 serves depot 3 at minute 7. The last depot is therefore served at minute 7.

Example 2

Input
legs = [[2,1,4]], depots = 2, origin = 1
Output
-1

The only leg runs from depot 2 to depot 1, and legs are one-way, so nothing ever leaves depot 1 and depot 2 stays unserved.

Constraints

  • 1 <= origin <= depots <= 100
  • 1 <= legs.length <= 6000
  • legs[i].length == 3
  • 1 <= u_i, v_i <= depots
  • u_i != v_i
  • 0 <= w_i <= 100
  • All the pairs (u_i, v_i) are unique. (i.e., no multiple legs.)

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def broadcast_time(legs: list[list[int]], depots: int, origin: int) -> int:
Java
public int broadcastTime(int[][] legs, int depots, int origin)

More on the same topics