LeetCode Problem 3650

Difficulty: 🟡 Medium
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

LeetCode 3650 - Minimum Cost Path with Edge Reversals

Problem Understanding

We are given a directed weighted graph with n nodes and a list of directed edges. Each edge u → v has a traversal cost w.

Normally, we may travel only along the original directed edges and pay the edge weight. However, every node has a special one-time switch. When we arrive at node u, we may use its switch at most once. Using the switch allows us to pick one incoming edge v → u, temporarily reverse it into u → v, and immediately traverse that reversed edge.

This temporary reversal has two important restrictions:

1. The reversed edge exists only for that single move.
2. Traversing the reversed edge costs 2 * w instead of w.

The switch belongs to a node, not to an edge. Once we use node u's switch, it can never be used again during the remainder of the path.

Our goal is to find the minimum total cost to travel from node 0 to node n - 1.

If no valid path exists, we return -1.

Understanding the State

The key difficulty is that the graph is not static. The set of available moves depends on which node switches have already been consumed.

Suppose we reach node u multiple times through different routes. One route may have already used the switch of node u, while another may not. These situations are fundamentally different because future options differ.

Therefore, the shortest-path state cannot be represented only by the current node.

Constraints Analysis

The constraints are:

• 2 <= n <= 5 * 10^4
• 1 <= edges.length <= 10^5
• 1 <= wi <= 1000

A brute-force search over all possible switch usages would be impossible.

The graph is large enough that we need roughly O((n + m) log n) or O(m log n) complexity.

The positive edge weights strongly suggest a shortest-path algorithm such as Dijkstra.

Important Edge Cases

A path may exist without any reversals. The algorithm should naturally choose such a path if it is cheapest.

The destination may only be reachable through one or more reversals. A solution that ignores reversed moves would fail.

The graph may be disconnected. In that case the answer should be -1.

A node may be revisited multiple times. We must correctly distinguish between arriving with its switch still available and arriving after its switch has already been used.

There may be multiple incoming edges into a node. When using a switch, any one of those incoming edges may be chosen for reversal.

Approaches

Brute Force

A brute-force solution would explore every possible path while keeping track of which node switches have already been consumed.

Whenever we arrive at a node, we could either:

• Follow any outgoing edge normally.
• Use the node's switch on any incoming edge that has not yet been used at that node.

Since every node may or may not have already consumed its switch, the state space contains up to 2^n possible switch configurations.

The search would quickly become infeasible even for small graphs.

Although this approach is correct because it explores every legal sequence of moves, it is far too slow for n = 50,000.

Key Observation

Notice what actually matters when standing at node u.

The switch of node u affects only moves originating from u.

Once we leave u, whether its switch remains unused no longer matters unless we return to u later.

This suggests splitting each node into two states:

• State 0: currently at node u, switch of u is still unused.
• State 1: currently at node u, switch of u has already been used.

From state 0:

• We may traverse normal outgoing edges and remain in state 0 of the destination.
• We may reverse any incoming edge and move to state 0 of the neighbor, because the switch consumed belongs to the node we are leaving, not the destination.

The crucial insight is that after performing a reversal from node u, we should remember that u's switch has been spent if we ever come back.

This can be modeled using a layered shortest-path graph where each node has two versions representing whether its local switch is available when we stand there.

The resulting graph has only 2n states and O(m) transitions, making Dijkstra feasible.

A cleaner interpretation is to build a state graph:

• (u, 0) = arrive at u with switch available.
• (u, 1) = arrive at u after consuming its switch.

Normal edges preserve the switch status of the current node state.

Using a reversal corresponds to traversing an incoming edge at doubled cost while transitioning appropriately.

Running Dijkstra on this expanded graph yields the optimal answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all switch usage combinations
Optimal	O((n + m) log n)	O(n + m)	Dijkstra on a two-state graph

Algorithm Walkthrough

State Definition

For every node u, maintain two shortest-path distances:

• dist[u][0]
• dist[u][1]

where:

• 0 means the switch at u is still available.
• 1 means the switch at u has already been used.

Graph Construction

Store:

• Outgoing adjacency list.
• Incoming adjacency list.

The outgoing list supports normal traversals.

The incoming list allows us to efficiently enumerate edges that could be reversed when standing at a node.

Dijkstra Initialization

1. Create a min-heap.
2. Initialize all distances to infinity.
3. Start from state (0, 0) because node 0 has not used its switch yet.
4. Push (0, 0, 0) into the heap, representing (cost, node, state).

Processing a State

1. Pop the minimum-cost state from the heap.
2. If this entry is stale, skip it.

Normal Edge Transitions

1. For every outgoing edge u → v with weight w:

• New cost = current cost + w.
• Move to (v, 0) because arriving at a node always means its own switch is initially unused.
• Relax the distance if improved.

Reversal Transitions

1. If we are in state (u, 0), the switch at u is still available.
2. Enumerate every incoming edge v → u with weight w.
3. Reverse it temporarily into u → v.
4. Travel along it with cost 2 * w.
5. The switch of u becomes consumed.
6. Move to node v.
7. Relax the resulting state.

Finish

1. Continue Dijkstra until the heap becomes empty.
2. The answer is the minimum distance among states corresponding to node n - 1.
3. If both distances remain infinity, return -1.

Why it Works

The expanded graph represents every legal situation that can occur during traversal. Every normal move and every valid reversal is encoded as an edge in the state graph with exactly the same cost as in the original problem. Therefore, every valid route in the original graph corresponds to a path in the state graph, and vice versa.

Since all edge weights are positive, Dijkstra's algorithm correctly computes the shortest path in the state graph. Consequently, the minimum distance found for node n - 1 is exactly the minimum achievable travel cost in the original problem.

Python Solution

from typing import List
import heapq

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        outgoing = [[] for _ in range(n)]
        incoming = [[] for _ in range(n)]

        for u, v, w in edges:
            outgoing[u].append((v, w))
            incoming[v].append((u, w))

        INF = 10**18
        dist = [INF] * n

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

        while pq:
            cost, u = heapq.heappop(pq)

            if cost != dist[u]:
                continue

            if u == n - 1:
                return cost

            for v, w in outgoing[u]:
                new_cost = cost + w
                if new_cost < dist[v]:
                    dist[v] = new_cost
                    heapq.heappush(pq, (new_cost, v))

            for v, w in incoming[u]:
                new_cost = cost + 2 * w
                if new_cost < dist[v]:
                    dist[v] = new_cost
                    heapq.heappush(pq, (new_cost, v))

        return -1

Implementation Explanation

The solution builds two adjacency lists.

outgoing[u] stores all original edges leaving node u. These correspond to normal moves that cost w.

incoming[u] stores all edges entering node u. When standing at u, any of these edges can be temporarily reversed, creating a move from u back to the source node at cost 2 * w.

After constructing the graph, standard Dijkstra's algorithm is executed.

The priority queue always expands the currently cheapest reachable node. Whenever a node is processed, we examine both kinds of legal moves:

• Original outgoing edges.
• Temporarily reversed incoming edges.

Both transitions simply create additional directed edges in the search space.

Because all transition costs are positive, Dijkstra guarantees that the first time we finalize a node's distance, we have found its minimum possible cost.

If node n - 1 is never reached, the answer is -1.

Go Solution

package main

import (
	"container/heap"
)

type Edge struct {
	to int
	w  int
}

type State struct {
	cost int
	node int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[:n-1]
	return item
}

func minCost(n int, edges [][]int) int {
	outgoing := make([][]Edge, n)
	incoming := make([][]Edge, n)

	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]
		outgoing[u] = append(outgoing[u], Edge{v, w})
		incoming[v] = append(incoming[v], Edge{u, w})
	}

	const INF int = 1 << 60

	dist := make([]int, n)
	for i := range dist {
		dist[i] = INF
	}

	dist[0] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, State{0, 0})

	for pq.Len() > 0 {
		cur := heap.Pop(pq).(State)

		if cur.cost != dist[cur.node] {
			continue
		}

		if cur.node == n-1 {
			return cur.cost
		}

		for _, e := range outgoing[cur.node] {
			newCost := cur.cost + e.w
			if newCost < dist[e.to] {
				dist[e.to] = newCost
				heap.Push(pq, State{newCost, e.to})
			}
		}

		for _, e := range incoming[cur.node] {
			newCost := cur.cost + 2*e.w
			if newCost < dist[e.to] {
				dist[e.to] = newCost
				heap.Push(pq, State{newCost, e.to})
			}
		}
	}

	return -1
}

Go-Specific Notes

The Go implementation mirrors the Python solution closely.

A custom priority queue is implemented using Go's container/heap package. Distances are stored as integers because the maximum possible path cost is well within 64-bit limits.

Slices are used for adjacency lists, providing efficient storage and traversal of graph edges.

Worked Examples

Example 1

Input:

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

Adjacency lists:

Node	Outgoing	Incoming
0	(1,3), (2,2)
1		(0,3), (3,1)
2	(3,4)	(0,2)
3	(1,1)	(2,4)

Initial state:

Heap	Distances
(0,0)	[0,∞,∞,∞]

Process node 0:

Move	Cost
0 → 1	3
0 → 2	2

Distances:

[0,3,2,∞]

Process node 2:

Move	Cost
2 → 3	6
reverse (0→2)	6

Distances:

[0,3,2,6]

Process node 1:

Move	Cost
reverse (3→1)	5
reverse (0→1)	9

Distance to node 3 becomes:

5

Node 3 is the destination.

Answer:

5

Example 2

Input:

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

Initial distances:

[0,∞,∞,∞]

Process node 0:

dist[2] = 1

Process node 2:

dist[1] = 2
dist[3] = 4

Process node 1:

dist[3] = min(4, 3)

Final distances:

[0,2,1,3]

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log n)	Dijkstra processes each edge relaxation through a priority queue
Space	O(n + m)	Distance array, heap, and adjacency lists

The graph stores each original edge twice, once in the outgoing list and once in the incoming list. Therefore adjacency storage is O(m). Dijkstra maintains a distance array of size n and a priority queue whose size is bounded by the number of relaxations, giving overall O(n + m) space usage.

Test Cases

s = Solution()

assert s.minCost(
    4,
    [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
) == 5  # official example 1

assert s.minCost(
    4,
    [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]
) == 3  # official example 2

assert s.minCost(
    2,
    [[0,1,5]]
) == 5  # smallest reachable graph

assert s.minCost(
    2,
    []
) == -1  # disconnected graph

assert s.minCost(
    3,
    [[1,0,2]]
) == 4  # destination reachable only through reversal

assert s.minCost(
    3,
    [[0,1,10],[1,2,10],[2,1,1]]
) == 20  # normal path better than reversal

assert s.minCost(
    4,
    [[0,1,1],[1,0,1],[1,2,1],[2,3,1]]
) == 3  # cycle in graph

assert s.minCost(
    5,
    [[0,1,2],[1,2,2],[2,3,2],[3,4,2]]
) == 8  # simple chain

assert s.minCost(
    4,
    [[0,1,100],[0,2,1],[2,3,1]]
) == 2  # choose cheaper branch

Test Summary

Test	Why
Example 1	Uses reversal to improve path
Example 2	Pure shortest path without reversal
Single edge	Smallest reachable instance
Empty graph	Unreachable destination
Reversal required	Ensures incoming-edge reversal works
Expensive reversal	Confirms algorithm chooses cheaper route
Graph with cycle	Verifies no infinite processing
Linear chain	Basic path accumulation
Multiple choices	Confirms shortest route selection

Edge Cases

Destination Is Unreachable

A graph may contain no path from node 0 to node n - 1, even after considering all possible reversals. A common bug is returning an uninitialized distance value. The implementation initializes all distances to infinity and returns -1 if the destination is never reached.

Reversal Creates the Only Valid Route

Sometimes no outgoing edge leads toward the destination, but reversing an incoming edge enables progress. An implementation that only explores original edges would incorrectly report failure. By explicitly iterating through incoming[u], the algorithm considers every legal reversal.

Cycles and Repeated Visits

Graphs may contain directed cycles. A naive graph traversal could repeatedly revisit nodes and never terminate. Dijkstra avoids this problem by maintaining the best known distance to every node and discarding stale heap entries. Therefore each useful relaxation strictly improves a distance, guaranteeing termination.

Multiple Incoming Edges

A node may have many incoming edges. Any of them can be reversed when standing at that node. The incoming adjacency list stores all such candidates, ensuring that every legal reversed move is evaluated and no potentially optimal path is missed.