A canal city has n islands 0 .. n-1 joined by undirected drawbridges
bridges[i] = [u, v, cross, period]. A bridge only lets you start crossing at times that are
multiples of period (0, period, 2*period, ...), from either side; the crossing then takes cross
minutes. You may wait on any island for as long as you like.
You are on island src at time 0. Return the earliest time you can be on island dst, or -1 if
it is unreachable.
Examples
Input: n = 3, bridges = [[0,1,2,5],[1,2,1,4],[0,2,10,1]], src = 0, dst = 2
Output: 5
Explanation: cross 0-1 at time 0 (arrive 2), wait until 4, cross 1-2 (arrive 5).
The direct bridge would arrive at 10.
Input: n = 3, bridges = [[0,1,1,1],[1,2,1,3]], src = 0, dst = 2
Output: 4
Constraints
1 <= n <= 10**4,0 <= len(bridges) <= 3 * 10**40 <= cross <= 10**4,1 <= period <= 10**4- Target
O(E log V)time.
Goals
- Compute the earliest departure time from a periodic schedule
- Use arrival time as the Dijkstra key
- Argue why waiting never hurts, so Dijkstra stays correct