3650. Minimum Cost Path with Edge Reversals

MediumGraphShortest PathHeap (Priority Queue)

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [uᵢ, vᵢ, wᵢ] represents a directed edge from node uᵢ to node vᵢ with cost wᵢ.

Each node uᵢ has a switch that can be used at most once. When you arrive at uᵢ and have not yet used its switch, you may activate it on one of its incoming edges vᵢ → uᵢ, reversing that edge to uᵢ → vᵢ, and immediately traverse it.

The reversal is only valid for that single move, and using a reversed edge costs 2 * wᵢ.

Your task is to return the minimum total cost to travel from node 0 to node n - 1. If reaching node n - 1 is not possible, return -1.

Key points to understand:

The graph is directed, so normally you can only travel along the direction uᵢ → vᵢ at cost wᵢ.
The switch mechanism effectively lets you traverse any edge in the reverse direction (vᵢ → uᵢ becomes uᵢ → vᵢ), but at double the cost (2 * wᵢ).
Since each reversal is valid for only a single move and applies per edge usage, every edge in the graph can be thought of as providing two possible movements: a forward move from uᵢ to vᵢ costing wᵢ, and a reverse move from vᵢ to uᵢ costing 2 * wᵢ.
The goal is to find the cheapest path from node 0 to node n - 1 while taking advantage of both forward and reversed traversals.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dijkstra's Algorithm?

This problem maps to Dijkstra's Algorithm through a short path in the full flowchart.

The problem finds the minimum-cost path with forward edges at cost w and reverse edges at cost 2w; Dijkstra computes the shortest path on this augmented graph.

Open in Flowchart

Intuition

The key observation is in how the switch mechanism actually works. When we arrive at a node and use its switch to reverse an incoming edge vᵢ → uᵢ into uᵢ → vᵢ, what we are really doing is moving against the original direction of an edge. In other words, the switch gives us a way to walk along any edge backwards, paying 2 * wᵢ instead of the usual wᵢ.

Notice that the switch's "at most once per node" and "single move" restrictions do not actually limit us in a meaningful way. Each individual edge can be considered independently: from the perspective of building movement options, every directed edge (uᵢ, vᵢ, wᵢ) offers exactly two ways to move:

A forward move from uᵢ to vᵢ costing wᵢ.
A reverse move from vᵢ to uᵢ costing 2 * wᵢ (achieved by using the switch at uᵢ).

This means we can transform the original problem into a simpler one. Instead of worrying about switches and reversals during traversal, we just build a new graph where each original edge contributes both of these movement options as separate edges. Once we have this graph, the problem reduces to a classic shortest path question: find the minimum cost to travel from node 0 to node n - 1.

Since all edge costs are non-negative (wᵢ and 2 * wᵢ are both positive), Dijkstra's algorithm is the natural choice for finding the shortest path. We start at node 0 with cost 0, repeatedly expand the cheapest reachable node, and relax its neighbors. The moment we pop node n - 1 from the priority queue, we have guaranteed the minimum cost to reach it. If the queue empties before we ever reach node n - 1, then it is unreachable and we return -1.

Pattern Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

Solution 1: Dijkstra's Algorithm

Based on the intuition above, we first construct a directed graph g where each original edge (u, v, w) contributes two traversal options:

A forward edge (u, v) with cost w, corresponding to normal traversal.
A reverse edge (v, u) with cost 2 * w, corresponding to using the switch.

In code, we build an adjacency list g, and for each input edge we append both options:

g = [[] for _ in range(n)]
for u, v, w in edges:
    g[u].append((v, w))
    g[v].append((u, w * 2))

Next, we apply Dijkstra's algorithm on graph g to compute the shortest path from node 0 to node n - 1.

We use the following data structures:

A priority queue pq, where each element is a tuple (d, u), meaning the current known cost to reach node u is d. The priority queue always pops the node with the smallest cost first.
A distance array dist, where dist[u] stores the minimum cost found so far from node 0 to node u. Initially, we set dist[0] = 0 and all other entries to infinity.

We start by pushing (0, 0) into the queue, indicating that the cost to reach node 0 is 0.

In each iteration, we perform the following steps:

Pop the node (d, u) with the minimum cost from the priority queue.
If d > dist[u], this entry is stale (an outdated, larger cost), so we skip it.
If u == n - 1, we have reached the target with the minimum cost, so we return d immediately.
Otherwise, we iterate over all neighbors (v, w) of node u. For each neighbor, we compute the new cost nd = d + w. If nd < dist[v], we update dist[v] = nd and push (nd, v) into the priority queue.

pq = [(0, 0)]
dist = [inf] * n
dist[0] = 0
while pq:
    d, u = heappop(pq)
    if d > dist[u]:
        continue
    if u == n - 1:
        return d
    for v, w in g[u]:
        nd = d + w
        if nd < dist[v]:
            dist[v] = nd
            heappush(pq, (nd, v))
return -1

If the priority queue becomes empty and node n - 1 was never popped, it means node n - 1 is unreachable, so we return -1.

Complexity Analysis:

Time complexity: O(m × log m), where m is the number of edges in the constructed graph (twice the number of input edges). Each edge may cause a push into the priority queue, and each push/pop operation costs O(log m).
Space complexity: O(n + m), for storing the adjacency list g, the dist array, and the priority queue.

Example Walkthrough

Let's trace through the solution with a concrete example.

Input:

n = 4
edges = [[0, 1, 5], [1, 2, 3], [0, 2, 10], [3, 2, 1]]

We want the minimum cost to travel from node 0 to node 3.

Step 1: Build the Graph with Forward and Reverse Edges

For each original edge (u, v, w), we add a forward edge (u → v) costing w, and a reverse edge (v → u) costing 2 * w.

Original Edge	Forward Option	Reverse Option
`[0, 1, 5]`	`0 → 1` (5)	`1 → 0` (10)
`[1, 2, 3]`	`1 → 2` (3)	`2 → 1` (6)
`[0, 2, 10]`	`0 → 2` (10)	`2 → 0` (20)
`[3, 2, 1]`	`3 → 2` (1)	`2 → 3` (2)

Resulting adjacency list g:

g[0] = [(1, 5), (2, 10)]
g[1] = [(2, 3), (0, 10)]
g[2] = [(1, 6), (0, 20), (3, 2)]
g[3] = [(2, 1)]

Notice that the only way to reach node 3 is via the reverse edge 2 → 3 costing 2 (the original edge [3, 2, 1] points the wrong way). Without the switch mechanism, node 3 would be unreachable.

Step 2: Run Dijkstra's Algorithm

Initialize:

dist = [0, ∞, ∞, ∞]
pq = [(0, 0)]

Iteration 1: Pop (0, 0). Node 0 is not the target. Relax neighbors:

0 → 1: nd = 0 + 5 = 5 < ∞ → dist[1] = 5, push (5, 1)
0 → 2: nd = 0 + 10 = 10 < ∞ → dist[2] = 10, push (10, 2)

State: dist = [0, 5, 10, ∞], pq = [(5, 1), (10, 2)]

Iteration 2: Pop (5, 1). Node 1 is not the target. Relax neighbors:

1 → 2: nd = 5 + 3 = 8 < 10 → dist[2] = 8, push (8, 2)
1 → 0: nd = 5 + 10 = 15 > 0 → skip

State: dist = [0, 5, 8, ∞], pq = [(8, 2), (10, 2)]

Iteration 3: Pop (8, 2). Node 2 is not the target. Relax neighbors:

2 → 1: nd = 8 + 6 = 14 > 5 → skip
2 → 0: nd = 8 + 20 = 28 > 0 → skip
2 → 3: nd = 8 + 2 = 10 < ∞ → dist[3] = 10, push (10, 3)

State: dist = [0, 5, 8, 10], pq = [(10, 2), (10, 3)]

Iteration 4: Pop (10, 2). But d = 10 > dist[2] = 8, so this entry is stale → skip.

State: pq = [(10, 3)]

Iteration 5: Pop (10, 3). Node 3 is the target → return 10.

Result

The minimum cost from node 0 to node 3 is 10, achieved via the path:

0 → 1 (cost 5)  →  1 → 2 (cost 3)  →  2 → 3 (reverse edge, cost 2)

Total: 5 + 3 + 2 = 10.

This example highlights the core idea: the reverse edge 2 → 3 (the switch applied to the original 3 → 2 edge) was essential to reach the destination, and Dijkstra naturally found the cheapest combination of forward and reverse moves.

Solution Implementation

1import heapq
2from math import inf
3from typing import List
4
5
6class Solution:
7    def minCost(self, n: int, edges: List[List[int]]) -> int:
8        # Build an adjacency list for the graph.
9        # For each directed edge u -> v with weight w:
10        #   - Traversing it in the original direction (u -> v) costs w.
11        #   - Traversing it in the reverse direction (v -> u) costs w * 2.
12        graph = [[] for _ in range(n)]
13        for u, v, w in edges:
14            graph[u].append((v, w))       # forward direction
15            graph[v].append((u, w * 2))   # reverse direction (double cost)
16
17        # Min-heap priority queue storing tuples of (current_distance, node).
18        # Start from node 0 with distance 0.
19        priority_queue = [(0, 0)]
20
21        # dist[i] holds the shortest known distance from node 0 to node i.
22        dist = [inf] * n
23        dist[0] = 0
24
25        # Standard Dijkstra's algorithm.
26        while priority_queue:
27            distance, node = heapq.heappop(priority_queue)
28
29            # Skip if we've already found a shorter path to this node.
30            if distance > dist[node]:
31                continue
32
33            # Early exit: the first time we pop the target node,
34            # its distance is guaranteed to be the minimum.
35            if node == n - 1:
36                return distance
37
38            # Relax all outgoing edges from the current node.
39            for neighbor, weight in graph[node]:
40                new_distance = distance + weight
41                if new_distance < dist[neighbor]:
42                    dist[neighbor] = new_distance
43                    heapq.heappush(priority_queue, (new_distance, neighbor))
44
45        # Node n - 1 is unreachable from node 0.
46        return -1
47

1class Solution {
2    public int minCost(int n, int[][] edges) {
3        // Build an adjacency list where each entry stores {neighbor, weight}.
4        // For every directed edge u -> v with weight w, we can:
5        //   - traverse it in the original direction at cost w
6        //   - traverse it in the reverse direction at cost w * 2
7        List<int[]>[] graph = new ArrayList[n];
8        Arrays.setAll(graph, key -> new ArrayList<>());
9        for (int[] edge : edges) {
10            int from = edge[0];
11            int to = edge[1];
12            int weight = edge[2];
13            graph[from].add(new int[] {to, weight});
14            graph[to].add(new int[] {from, weight * 2});
15        }
16
17        // Use a large sentinel value to represent "unreached" distances,
18        // while avoiding integer overflow during additions.
19        final int INF = Integer.MAX_VALUE / 2;
20        int[] distance = new int[n];
21        Arrays.fill(distance, INF);
22        distance[0] = 0;
23
24        // Min-heap ordered by the current shortest distance (Dijkstra's algorithm).
25        // Each element is {distance, node}.
26        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
27        minHeap.offer(new int[] {0, 0});
28
29        while (!minHeap.isEmpty()) {
30            int[] current = minHeap.poll();
31            int dist = current[0];
32            int node = current[1];
33
34            // Skip stale entries whose recorded distance is outdated.
35            if (dist > distance[node]) {
36                continue;
37            }
38
39            // Reaching the last node guarantees the minimal cost due to Dijkstra's
40            // greedy property, so we can return immediately.
41            if (node == n - 1) {
42                return dist;
43            }
44
45            // Relax all outgoing edges from the current node.
46            for (int[] neighbor : graph[node]) {
47                int next = neighbor[0];
48                int weight = neighbor[1];
49                int newDist = dist + weight;
50                if (newDist < distance[next]) {
51                    distance[next] = newDist;
52                    minHeap.offer(new int[] {newDist, next});
53                }
54            }
55        }
56
57        // The destination node is unreachable.
58        return -1;
59    }
60}
61

1class Solution {
2public:
3    int minCost(int n, vector<vector<int>>& edges) {
4        using PII = pair<int, int>; // {distance, node}
5
6        // Build adjacency list. Traversing an edge in its given direction
7        // costs w, while traversing it in reverse costs w * 2.
8        vector<vector<PII>> graph(n);
9        for (auto& edge : edges) {
10            int u = edge[0], v = edge[1], w = edge[2];
11            graph[u].push_back({v, w});     // forward direction: cost w
12            graph[v].push_back({u, w * 2}); // reverse direction: cost 2 * w
13        }
14
15        const int inf = INT_MAX / 2;
16
17        // dist[i] holds the shortest known cost from node 0 to node i.
18        vector<int> dist(n, inf);
19        dist[0] = 0;
20
21        // Min-heap ordered by distance for Dijkstra's algorithm.
22        priority_queue<PII, vector<PII>, greater<PII>> pq;
23        pq.push({0, 0});
24
25        while (!pq.empty()) {
26            auto [d, u] = pq.top();
27            pq.pop();
28
29            // Skip stale entries whose recorded distance is outdated.
30            if (d > dist[u]) {
31                continue;
32            }
33
34            // Reached the destination with the minimum cost.
35            if (u == n - 1) {
36                return d;
37            }
38
39            // Relax all edges going out from the current node.
40            for (auto& [v, w] : graph[u]) {
41                int nd = d + w;
42                if (nd < dist[v]) {
43                    dist[v] = nd;
44                    pq.push({nd, v});
45                }
46            }
47        }
48
49        // Destination is unreachable from node 0.
50        return -1;
51    }
52};
53

1// Priority queue comparator type: returns negative if a has higher priority than b
2type Comparator<T> = (a: T, b: T) => number;
3
4// Minimal binary-heap based priority queue used by the Dijkstra routine.
5class PriorityQueue<T> {
6    private heap: T[] = [];
7    private readonly compare: Comparator<T>;
8
9    constructor(compare: Comparator<T>) {
10        this.compare = compare;
11    }
12
13    // Whether the queue currently holds no elements.
14    isEmpty(): boolean {
15        return this.heap.length === 0;
16    }
17
18    // Insert a new value and restore the heap order by sifting it up.
19    enqueue(value: T): void {
20        this.heap.push(value);
21        this.siftUp(this.heap.length - 1);
22    }
23
24    // Remove and return the smallest element according to the comparator.
25    dequeue(): T {
26        const top = this.heap[0];
27        const last = this.heap.pop()!;
28        if (this.heap.length > 0) {
29            this.heap[0] = last;
30            this.siftDown(0);
31        }
32        return top;
33    }
34
35    // Move the element at index up until the heap property holds.
36    private siftUp(index: number): void {
37        while (index > 0) {
38            const parent = (index - 1) >> 1;
39            if (this.compare(this.heap[index], this.heap[parent]) >= 0) {
40                break;
41            }
42            [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
43            index = parent;
44        }
45    }
46
47    // Move the element at index down until the heap property holds.
48    private siftDown(index: number): void {
49        const size = this.heap.length;
50        while (true) {
51            const left = index * 2 + 1;
52            const right = index * 2 + 2;
53            let smallest = index;
54            if (left < size && this.compare(this.heap[left], this.heap[smallest]) < 0) {
55                smallest = left;
56            }
57            if (right < size && this.compare(this.heap[right], this.heap[smallest]) < 0) {
58                smallest = right;
59            }
60            if (smallest === index) {
61                break;
62            }
63            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
64            index = smallest;
65        }
66    }
67}
68
69/**
70 * Compute the minimum cost to travel from node 0 to node n - 1.
71 *
72 * Each undirected input edge [u, v, w] can be traversed:
73 *   - in the forward direction (u -> v) at cost w, or
74 *   - in the reverse direction (v -> u) at cost w * 2.
75 *
76 * This is a standard single-source shortest path problem solved with
77 * Dijkstra's algorithm over the asymmetric edge weights.
78 *
79 * @param n     Number of nodes, labeled 0 .. n - 1.
80 * @param edges List of directed-capable edges [u, v, w].
81 * @returns     Minimum total cost, or -1 if node n - 1 is unreachable.
82 */
83function minCost(n: number, edges: number[][]): number {
84    // Adjacency list: graph[u] holds [neighbor, weight] pairs.
85    const graph: number[][][] = Array.from({ length: n }, () => []);
86    for (const [u, v, w] of edges) {
87        graph[u].push([v, w]);      // forward direction costs w
88        graph[v].push([u, w * 2]);  // reverse direction costs 2 * w
89    }
90
91    // dist[i] = best known cost to reach node i from node 0.
92    const dist: number[] = Array(n).fill(Infinity);
93    dist[0] = 0;
94
95    // Min-heap ordered by accumulated distance.
96    const pq = new PriorityQueue<number[]>((a, b) => a[0] - b[0]);
97    pq.enqueue([0, 0]); // [distance, node]
98
99    while (!pq.isEmpty()) {
100        const [d, u] = pq.dequeue();
101
102        // Skip stale entries that were superseded by a shorter path.
103        if (d > dist[u]) {
104            continue;
105        }
106
107        // Reaching the target with the smallest distance gives the answer.
108        if (u === n - 1) {
109            return d;
110        }
111
112        // Relax all outgoing edges from u.
113        for (const [v, w] of graph[u]) {
114            const nd = d + w;
115            if (nd < dist[v]) {
116                dist[v] = nd;
117                pq.enqueue([nd, v]);
118            }
119        }
120    }
121
122    // Target node could not be reached.
123    return -1;
124}
125

Time and Space Complexity

Time Complexity: O(n + m × log m)

This code implements Dijkstra's algorithm using a priority queue (min-heap) to find the shortest path from node 0 to node n - 1.

Graph construction: Building the adjacency list g iterates over all m edges once, with each edge adding two directed entries. This takes O(n + m) time (O(n) to initialize the lists, O(m) to process the edges).
Dijkstra's main loop: Each edge can trigger at most one heappush operation, so the heap holds at most O(m) entries. Each heappop and heappush costs O(log m). Since there are at most O(m) such operations, this part is O(m × log m).

Combining these, the overall time complexity is O(n + m × log m), where n is the number of nodes and m is the number of edges.

Space Complexity: O(n + m)

The adjacency list g stores two entries per edge, requiring O(n + m) space.
The dist array uses O(n) space.
The priority queue pq can hold up to O(m) entries.

Therefore, the total space complexity is O(n + m), where n is the number of nodes and m is the number of edges.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to handle the reverse edge (only building forward edges)

The most common mistake is to treat this as a standard shortest-path problem and only add the forward edge (u, v, w) to the adjacency list, ignoring the switch mechanism entirely:

# WRONG: only forward edges
for u, v, w in edges:
    graph[u].append((v, w))   # missing the reverse traversal!

This silently produces incorrect answers because it discards a whole class of valid moves. The problem explicitly states that each edge offers two traversal options. The fix is to always add both directions when constructing the graph:

for u, v, w in edges:
    graph[u].append((v, w))       # forward: u -> v costs w
    graph[v].append((u, w * 2))   # reverse: v -> u costs 2 * w

Reasoning: Since the switch reversal applies per single move (not permanently changing the graph), it is equivalent to a static graph where every edge can be walked backward at double cost. Modeling it this way lets a plain Dijkstra solve the whole problem without tracking switch state.

Pitfall 2: Misusing the "at most once per switch" constraint as a global state

Some readers worry that the "at most once" wording requires tracking which switches have been used (e.g., via a visited-switch bitmask or an expanded state space). This leads to an exponential blow-up and an over-engineered solution.

Why it's not needed: A switch reversal lets you arrive at uᵢ via a reversed incoming edge and immediately traverse it. Because the reversed edge is consumed in that single move, and any shortest path in a non-negative-weight graph never benefits from reusing the same edge, the per-node "use once" limit is automatically respected by Dijkstra. There is no scenario where the optimal path would need to reverse the same edge twice. Therefore, no extra state is required — the simple two-directional graph captures the constraint correctly.

Pitfall 3: Using a `visited` set instead of stale-entry checking

A frequent Dijkstra bug is marking nodes as "visited" and pushing duplicate entries without the staleness guard:

# RISKY: relying on a visited set while still pushing duplicates
visited = set()
while priority_queue:
    distance, node = heapq.heappop(priority_queue)
    if node in visited:
        continue
    visited.add(node)
    ...

While a correctly implemented visited set works, mixing it with missing the distance > dist[node] check causes outdated, larger-cost entries to be processed and relaxed unnecessarily. The cleaner and standard approach is the stale-check used in the solution:

if distance > dist[node]:
    continue

This skips any entry whose distance no longer matches the best-known distance, keeping the algorithm both correct and efficient.

Pitfall 4: Integer overflow / wrong infinity sentinel (language-dependent)

In Python this is a non-issue thanks to arbitrary-precision integers and math.inf. In languages like Java or C++, however, initializing dist with Integer.MAX_VALUE and then computing new_distance = distance + weight can overflow into a negative number, causing the relaxation check new_distance < dist[neighbor] to wrongly succeed.

Solution: Use a sufficiently large but safe sentinel (e.g., Long or 0x3f3f3f3f in C++), or guard against overflow before adding. In Python, simply rely on inf as shown.

Pitfall 5: Edge cases — `n == 1` or self-relevant inputs

If n == 1, the source and target are the same node, and the answer should be 0. The provided code handles this correctly because dist[0] = 0 and the early-exit check if node == n - 1 triggers immediately when (0, 0) is popped. Still, it's worth verifying this boundary explicitly, since a naive implementation that only checks the target after relaxing edges might miss returning 0 for a trivial single-node graph.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know