Time for a signal to reach every node

Scenario

A monitoring system sends a heartbeat signal from one server to the whole network. The network has n servers, numbered 0 to n - 1, joined by one-way links. Each link takes some milliseconds to carry the signal, and a server passes it on to every link that leaves it as soon as it arrives.

You work on the monitoring system. It must show how long the network takes to hear the signal: the moment the last server receives it, or an alert if some server never does.

Your task

Write signal_time(n, links, source).

n is the number of servers.
links[i] = [a, b, ms] is a one-way link from server a to server b that takes ms milliseconds.
source is the server that sends the signal at time 0.
Return the time at which the last server receives the signal. Return -1 when some server never receives it. A network of one server returns 0.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, links = [[0, 1, 2], [0, 2, 5], [1, 2, 1], [2, 3, 3]], source = 0
Output: 6

Each heap entry is (arrival time, server), and the earliest leaves first.

Taken from the heap	Links relaxed	Heap after
(0, server 0)	0 to 1 gives 2, 0 to 2 gives 5	(2, 1), (5, 2)
(2, server 1)	1 to 2 gives 3	(3, 2), (5, 2)
(3, server 2)	2 to 3 gives 6	(5, 2), (6, 3)
(5, server 2)	stale: server 2 already has 3	(6, 3)
(6, server 3)	no links leave it

The arrival times are 0, 2, 3 and 6, and the largest is 6.

Example 2#

text2 lines

Input:  n = 3, links = [[0, 1, 4]], source = 0
Output: -1

No link leads to server 2, so it never hears the signal.

Example 3#

text2 lines

Input:  n = 1, links = [], source = 0
Output: 0

The only server is the sender, so everyone has the signal at time 0.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(links) ≤ 200,000, and every link is [a, b, ms] with 0 ≤ a, b < n, a ≠ b and 1 ≤ ms ≤ 100
0 ≤ source < n

What does n ≤ 10^5 tell you?

There can be 100,000 servers and 200,000 links. One Dijkstra run costs about one heap operation per link, which is a few million steps. Starting a separate search from the source for every server would be 100,000 runs, which is billions of steps. A single run from the source already gives the time to every server.

Scenario

You work on the monitoring system. It must show how long the network takes to hear the signal: the moment the last server receives it, or an alert if some server never does.

Your task

Write signal_time(n, links, source).

n is the number of servers.
links[i] = [a, b, ms] is a one-way link from server a to server b that takes ms milliseconds.
source is the server that sends the signal at time 0.
Return the time at which the last server receives the signal. Return -1 when some server never receives it. A network of one server returns 0.

Examples

Example 1 (traced)#

text2 lines

Input:  n = 4, links = [[0, 1, 2], [0, 2, 5], [1, 2, 1], [2, 3, 3]], source = 0
Output: 6

Each heap entry is (arrival time, server), and the earliest leaves first.

Taken from the heap	Links relaxed	Heap after
(0, server 0)	0 to 1 gives 2, 0 to 2 gives 5	(2, 1), (5, 2)
(2, server 1)	1 to 2 gives 3	(3, 2), (5, 2)
(3, server 2)	2 to 3 gives 6	(5, 2), (6, 3)
(5, server 2)	stale: server 2 already has 3	(6, 3)
(6, server 3)	no links leave it

The arrival times are 0, 2, 3 and 6, and the largest is 6.

Example 2#

text2 lines

Input:  n = 3, links = [[0, 1, 4]], source = 0
Output: -1

No link leads to server 2, so it never hears the signal.

Example 3#

text2 lines

Input:  n = 1, links = [], source = 0
Output: 0

The only server is the sender, so everyone has the signal at time 0.

Constraints

1 ≤ n ≤ 100,000
0 ≤ len(links) ≤ 200,000, and every link is [a, b, ms] with 0 ≤ a, b < n, a ≠ b and 1 ≤ ms ≤ 100
0 ≤ source < n

What does n ≤ 10^5 tell you?