Understanding the Problem

The graph is directed and weighted. You start at node 0 and want to reach node n-1 with minimum cost. The complication is the per-node switch: when you arrive at a node, you can pick one of its incoming edges, reverse it, and walk along it that one time. Traversing a reversed edge costs double (2 * w instead of w).

The reversal can be modeled directly in the graph. For every original edge [u, v, w], add a reverse edge from v to u with cost 2 * w. This reverse edge represents arriving at node v and using its switch to reverse the u → v edge into v → u.

After this augmentation, the problem becomes a standard shortest path from node 0 to node n-1 on a graph with non-negative edge weights, which Dijkstra's algorithm solves directly.

Key Constraints:

1 <= w_i <= 1000 --> All weights are positive (the reverse edges, at 2 * w, are positive too), so Dijkstra applies. No negative edges means no need for Bellman-Ford.
2 <= n <= 5 * 10^4 and 1 <= edges.length <= 10^5 --> After adding one reverse edge per original edge, the graph has up to 2 * 10^5 edges. A min-heap Dijkstra at O(m log m) handles this; an O(n^2) approach would not.
The maximum possible path cost is bounded by roughly n * 2 * w_max, under 10^8, so a 32-bit signed integer holds every distance without overflow.

Approach 1: Dijkstra with Reverse Edges

Intuition

For every original edge u → v with weight w, add a reverse edge v → u with weight 2 * w. This reverse edge represents one specific move: arrive at node v, use its switch to reverse the u → v edge, and traverse it back to u at double cost. Once both the original and reverse edges are in the graph, every legal move in the problem corresponds to following one edge, and the answer is the shortest path from node 0 to node n-1.

Building the reverse edges takes a single pass over the input. Running Dijkstra on the augmented graph then finds the shortest distance to node n-1, or reports -1 if it is unreachable.

Correctness

The "switch used at most once per node" rule appears to need extra state, but the augmented graph satisfies it without any tracking. All edge weights are positive, so the shortest path Dijkstra returns is simple: it visits every node at most once. A reverse edge leaving node v corresponds to using v's switch, and a simple path leaves each node at most once, so each switch is used at most once along the optimal route. No bookkeeping is required.

The cost also matches the problem exactly. Following an original edge u → v costs w, and following a reverse edge v → u costs 2 * w, which is the stated price of a reversal. So a path in the augmented graph and the corresponding sequence of moves have equal cost, and minimizing one minimizes the other.

Algorithm

Build an adjacency list. For each edge [u, v, w], add (v, w) to adj[u] (original edge) and (u, 2*w) to adj[v] (reverse edge).
Initialize a distance array dist[] with infinity for all nodes. Set dist[0] = 0.
Push (0, 0) (cost, node) into a min-heap.
While the heap is not empty:

Pop (cost, node) with the smallest cost.
If node == n-1, return cost.
If cost > dist[node], skip (already found a shorter path).
For each neighbor (next, weight) in adj[node], if cost + weight < dist[next], update dist[next] and push into the heap.

Return -1 (node n-1 is unreachable).

Example Walkthrough

1Start: dist[0]=0, push (0,0) to heap. Adjacency: 0→1(3), 0→2(2), 1→0(6), 1→3(2), 2→3(4), 2→0(4), 3→1(1), 3→2(8)

[0, INF, INF, INF]

1/5

Code

Complexity Analysis

Time Complexity: O(n + m log m). Building the adjacency list is O(m). Dijkstra processes each edge at most once and each heap operation is O(log m), where m is the number of edges (doubled to 2m after adding reverse edges).
Space Complexity: O(n + m). The adjacency list stores 2m edges. The dist array and heap use O(n) and O(m) space respectively.

Minimum Cost Path with Edge Reversals