Network delay time

mediumDijkstra's shortest pathsHeaps target 25 min

Network delay time

Not solved yetLeetCode 743. Network Delay Time

There are n servers labeled 1 to n. Each item of times is a one-way link [u, v, w]: a message sent from server u reaches server v after w milliseconds. A link from u to v gives no way back from v to u.

Server k creates a message at time 0. Every server passes the message on along all of its outgoing links the moment it first receives it. Return the time at which the last server receives the message. If some server never receives it, return -1.

Example 1

Inputtimes = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]], n = 4, k = 1Output4

Server 3 hears at 1. The direct link reaches server 2 at 4, but the route through 3 gets there at 1 + 2 = 3. Server 4 hears at 3 + 1 = 4, the latest of all.

Example 2

Inputtimes = [[1, 2, 2], [3, 1, 1]], n = 3, k = 1Output-1

The link [3, 1, 1] only goes from 3 to 1. No link leads into server 3, so it never hears.

Constraints

1 ≤ k ≤ n ≤ 2 × 10⁴
0 ≤ len(times) ≤ 10⁵
Every link is [u, v, w] with 1 ≤ u, v ≤ n, u ≠ v and 0 ≤ w ≤ 100. No pair (u, v) appears twice.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern