A rail network has n stations 0 .. n-1. Train services are directed: trains[i] = [u, v, minutes]
is a service from u to v taking minutes. Every time a traveller passes through a station on
the way (arrives there and later leaves again) they spend layover[s] minutes changing platforms. The
departure station src and the final station dst have no layover.
Return the minimum total travel time from src to dst, or -1 if dst cannot be reached.
Examples
Input: n = 4, trains = [[0,1,2],[1,3,2],[0,2,3],[2,3,3]], layover = [0,10,1,0], src = 0, dst = 3
Output: 7
Explanation: via 1 costs 2 + 10 + 2 = 14; via 2 costs 3 + 1 + 3 = 7.
Input: n = 3, trains = [[0,1,5]], layover = [4,4,4], src = 0, dst = 2
Output: -1
Constraints
1 <= n <= 10**4,0 <= len(trains) <= 3 * 10**4,0 <= minutes, layover[s] <= 10**4- Target
O(E log V)time.
Goals
- Fold a per-station cost into the edges leaving that station
- Exempt the departure station from the layover
- Run Dijkstra on the adjusted weights