#178MediumGraphs· Dijkstra's Shortest Paths

Signal Delay to All Stations

A radio network has `n` relay stations numbered `1` to `n`. A directed link `[u, v, w]` means a signal sent by station `u` reaches station `v` after `w` milliseconds. Stations forward the signal the instant they receive it, and they can forward it along several links at once. At time 0 a signal is emitted from station `k`. Return the time at which **every** station has received it, which is the largest of the shortest arrival times. If some station can never receive the signal, return `-1`.

Input format

`links`: an array of triples `[u, v, w]`; `n`: the number of stations; `k`: the source station.

Output format

An integer: the time until all stations have the signal, or -1 if some station is unreachable.

Examples

Input: links = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2

Output: 2

From station 2 the signal reaches 1 and 3 at time 1 and station 4 at time 2, so everyone has it at time 2.

Input: links = [[1, 2, 1]], n = 2, k = 1

Output: 1

Station 2 gets the signal after 1 millisecond.

Input: links = [[1, 2, 1]], n = 2, k = 2

Output: -1

Station 2 has no outgoing links, so station 1 is never reached: -1.

Constraints

1 <= k <= n <= 500
1 <= links.length <= 6000
1 <= u, v <= n and u != v
1 <= w <= 100
Each ordered pair (u, v) appears at most once.

Study first

#graph
#shortest-path
#dijkstra
#heap