Minimum Cost Path with Edge Reversals
You receive a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [u i, v i, w i ] represents a directed edge from node u i to node v i with cost w i.
Each node u i has a switch that can be used at most once: when you arrive at u i and have not yet used its switch, you may activate it on one of its incoming edges v i → u i reverse that edge to u i → v i and immediately traverse it.
The reversal is only valid for that single move, and using a reversed edge costs 2 * w i.
Produce the minimum total cost to travel from node 0 to node n - 1. If it is not possible, produce -1.
Input: n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
Output: 5
Explanation:
-
Use the path
0 → 1(cost 3). -
At node 1 reverse the original edge
3 → 1into1 → 3and traverse it at cost2 * 1 = 2. -
Total cost is
3 + 2 = 5.
Input: n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]
Output: 3
Explanation:
-
No reversal is needed. Take the path
0 → 2(cost 1), then2 → 1(cost 1), then1 → 3(cost 1). -
Total cost is
1 + 1 + 1 = 3.
Constraints
2 <= n <= 5 * 10^41 <= edges.length <= 10^5edges[i] = [u i, v i, w i ]0 <= u i, v i <= n - 11 <= w i <= 1000
Did this problem appear in one of your interviews?
Responses stay private.