Two warehouses a and b both need to ship goods to store c. The road network has n nodes
0 .. n-1 and directed roads roads[i] = [u, v, cost] (cost >= 0). The company must pay to
maintain a set of roads such that c is reachable from a and from b using only maintained roads.
A road used by both shipments is paid only once.
Return the minimum total maintenance cost, or -1 if it is impossible.
Examples
Input: n = 5, roads = [[0,2,2],[1,2,2],[2,4,5],[0,4,8],[1,4,8]], a = 0, b = 1, c = 4
Output: 9
Explanation: maintain 0->2, 1->2 and 2->4; the shared road 2->4 is paid once.
Input: n = 3, roads = [[0,2,1],[1,2,1]], a = 0, b = 1, c = 2
Output: 2
Constraints
1 <= n <= 10**4,0 <= len(roads) <= 3 * 10**4,0 <= cost <= 10**5a,b,cneed not be distinct.- Target
O(E log V)time.
Goals
- Run Dijkstra on the reversed graph to get distances *to* a node
- Combine three distance arrays through a meeting node
- Explain why the optimal road set looks like a 'Y'