Buses With a Boarding Wait

A town has n stops 0 .. n-1. You can walk along undirected footpaths walks[i] = [u, v, minutes], or ride buses. Bus line j visits the stops routes[j] in that order and only in that direction (a route may visit a stop more than once); travelling between two consecutive stops of line j takes ride[j] minutes.

Getting on a bus at any stop of its route costs board minutes of waiting, every time you board (also when you board the same line again). While on a bus you may stay aboard through as many stops as you like and get off at any stop on its route for free.

You start on foot at stop src. Return the minimum number of minutes to reach stop dst, or -1 if it is impossible. If src == dst the answer is 0.

Examples

Input:  n = 5, walks = [[0,4,30]], routes = [[0,1,2,3],[3,4]], ride = [2,5],
        board = 4, src = 0, dst = 4
Output: 19
Explanation: board line 0 (4), ride 3 segments (6), change at stop 3 to
line 1 (4 + 5). Walking takes 30.

Input:  n = 4, walks = [], routes = [[0,1],[1,2,3],[0,3]], ride = [1,1,9],
        board = 5, src = 0, dst = 3
Output: 13

Input:  n = 3, walks = [], routes = [[0,1,2]], ride = [1], board = 2, src = 2, dst = 0
Output: -1

Constraints

• 1 <= n <= 2 * 10**4, 0 <= len(walks) <= 3 * 10**4, 0 <= minutes <= 10**4
• 0 <= len(routes), each route has at least one stop, and the routes hold at most 4 * 10**4 stops in total (a single route may be very long)
• 0 <= ride[j] <= 100, 0 <= board <= 1000

Goals

• Model 'which bus am I on' as part of the search state
• Charge a boarding cost once per boarding, not once per stop
• Keep the state graph linear in the total length of the routes