An electric delivery van drives on undirected roads roads[i] = [u, v, minutes] between n
junctions 0 .. n-1 (parallel roads and loops are possible). Its battery is low, so its route from
src to dst must pass through at least one junction listed in chargers (the start or the
end junction counts if it is a charger).
A route is a sequence of roads, each starting where the previous one ended; junctions and roads may be repeated. Two routes are different if their sequences of road indices differ.
Return [best, count]: the minimum number of minutes of a valid route and the number of valid
routes that take exactly best minutes, modulo 10**9 + 7. If there is no valid route, return
[-1, 0].
Examples
Input: n = 4, roads = [[0,1,1],[1,3,1],[0,2,1],[2,3,1]], chargers = [2], src = 0, dst = 3
Output: [2, 1]
Input: n = 4, roads = [[0,1,2],[1,2,2],[1,3,1],[1,3,1]], chargers = [3], src = 0, dst = 2
Output: [6, 4]
Explanation: the van must detour 1-3-1; it can go out on either road 2 or road 3
and come back on either, giving 4 routes of 2 + 1 + 1 + 2 = 6 minutes.
Input: n = 3, roads = [[0,1,1],[1,2,1]], chargers = [0, 1, 2], src = 0, dst = 2
Output: [2, 1]
Explanation: one route, even though it passes three chargers.
Constraints
1 <= n <= 2 * 10**4,0 <= len(roads) <= 4 * 10**4,1 <= minutes <= 10**4chargersholds distinct junctions (possibly none).
Goals
- Add a 'have I charged yet' flag to the Dijkstra state
- Count shortest walks in the layered graph while Dijkstra runs
- Avoid double counting routes that pass several chargers