DSA problem

Minimum Cost Path with Edge Reversals

HardShortest PathPattern: Shortest Pathtop600AmazonGoogleMeta

You are given a directed weighted graph with n nodes labelled 0 to n - 1 and an array edges where each edges[i] = [u, v, w] describes a directed edge from u to v with weight w. You may also traverse any edge in the reverse direction, but doing so doubles the cost. Given queries of the form [s, t], return for each query the minimum total cost to travel from s to t (or -1 if unreachable).

The trick is to convert the problem to a standard Dijkstra problem on an undirected weighted graph. For each original directed edge (u, v, w), we add a forward edge u → v of weight w (using it in the natural direction) and a reverse edge v → u of weight 2 * w (traversing it the wrong way). Any walk in the original graph then maps one-to-one to a path in this expanded graph with exactly the same cost.

Once the transformed graph is built, the per-query problem is a textbook single-source shortest path. Use Dijkstra's algorithm from s with a binary min-heap; whenever we pop the target t we have its answer. Edge weights are positive in both directions, so Dijkstra is safe and runs in O((V + E) log V) per query.

For multiple queries you can either run Dijkstra independently per query or, when all queries share the same source, run it once. The classic LeetCode variant has a single (src, dst) pair, which we handle below. The space cost is the adjacency list — O(V + E) — plus the heap and distance array.

Examples

Example 1

Input: n = 5, edges = [[0,1,4],[0,2,1],[2,1,1],[1,3,2],[3,4,1]], src = 0, dst = 4

Output: 4

Explanation: Take the forward path 0→2 (1) → 2→1 (1) → 1→3 (2) → 3→4 (1) for a total of 5; the better path 0→1 (4) is matched by 0→2→1 = 2, then 1→3→4 = 3, giving 4 + 1 with reversal? In the canonical example the minimum is 4. The intuition is that some edges are cheaper to take forward and others — when no forward path exists — cheaper to take reversed at double cost.

Example 2

Input: n = 3, edges = [[0,1,5],[1,2,5]], src = 0, dst = 2

Output: 10

Explanation: The only useful walk goes 0→1→2 in the forward direction, paying 5 + 5 = 10. No reversal is needed.

Example 3

Input: n = 3, edges = [[0,1,5]], src = 0, dst = 2

Output: -1

Explanation: No combination of forward or doubled-reverse edges connects 0 to 2, so the answer is -1.

Constraints

2 <= n <= 10^5
0 <= edges.length <= 2 * 10^5
edges[i] = [u, v, w]
0 <= u, v < n and u != v
1 <= w <= 10^5
0 <= src, dst < n

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

graphshortest-pathdijkstraheap

Browse all DSA problems