Road crews want to schedule repairs without slowing down the commute from district s to district
t. The map has n districts 0 .. n-1 and undirected roads roads[i] = [u, v, minutes]
(parallel roads and roads from a district to itself are possible).
A road is vital if every fastest route from s to t drives along it, so closing it would
make the commute strictly slower (or impossible). Return the sorted list of indices of the vital
roads. If t cannot be reached from s, return [].
Examples
Input: n = 5, roads = [[0,1,2],[1,2,1],[1,3,1],[2,4,1],[3,4,1],[0,4,5]], s = 0, t = 4
Output: [0]
Explanation: the fastest time is 4, via 0-1-2-4 or 0-1-3-4. Both use road 0.
Input: n = 4, roads = [[0,1,1],[1,2,1],[2,3,1],[0,2,2],[1,3,2]], s = 0, t = 3
Output: []
Explanation: 0-1-2-3, 0-2-3 and 0-1-3 all take 3 minutes. Every road is on
some fastest route, but no road is on all of them.
Input: n = 3, roads = [[0,1,4]], s = 0, t = 2
Output: []
Constraints
2 <= n <= 2 * 10**4,0 <= len(roads) <= 5 * 10**4,1 <= minutes <= 10**4,s != t- Target
O(E log V)time: closing each road in turn and rerunning a search is far too slow.
Goals
- Build the set of roads that lie on some fastest route with two Dijkstra runs
- See each such road as a time interval between its two ends
- Decide which roads are used by every fastest route without enumerating routes