Navigating a graph is usually a one-way street, but what if you could briefly flip the direction of traffic to reach your destination? This problem challenges us to find the most efficient route when we have the special ability to reverse edges at a specific cost. It is a fantastic way to learn how to adapt classic shortest-path algorithms to handle unconventional rules.
You're given:
- A directed graph with nodes and a list of weighted edges.
- A special "switch" at each node that allows you to reverse one incoming edge once you arrive there.
- A cost rule: traversing a normal edge costs , while traversing a reversed edge costs .
Your goal:
Find the minimum total cost to travel from node 0 to node . If the destination is unreachable, return -1.
Example:
Example 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 → 1 into 1 → 3 and traverse it at cost 2 * 1 = 2.
Total cost is 3 + 2 = 5.
Example 2:
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), then 2 → 1 (cost 1), then 1 → 3 (cost 1).
Total cost is 1 + 1 + 1 = 3.
Intuition: The "Ghost" Edge Strategy
At first glance, the rule about "reversing an edge only once upon arrival" sounds like we need to keep track of a lot of state. however, because we can only use the reversal immediately to move to the next node, we can simplify our thinking.
Essentially, every original directed edge with weight provides two possibilities:
- Move from to normally for cost .
- If we are at , we can use the switch to turn the edge into for cost .
By adding these "reverse options" as additional edges into our graph from the start, we transform the problem into a standard shortest-path search. Since all weights are non-negative, Dijkstra's Algorithm is the perfect tool for the job.
Walkthrough: Understanding the Examples
Example 1:
- Nodes: 4, Edges:
[[0,1,3],[3,1,1],[2,3,4],[0,2,2]] - Possible moves from node 0:
To node 1 (cost 3) or node 2 (cost 2).
If we go :
At node 1, we see an incoming edge from node 3 (
3 -> 1weight 1). We reverse it to go for cost .Total cost: .
If we go :
At node 2, there are no incoming edges to reverse that help us get closer to node 3.
The path is the cheapest. Output: 5.
Code Blocks
C++
class Solution {
public:
int minCost(int n, vector<vector<int>>& edges) {
// Build adjacency list with both original and reversed edges
vector<vector<pair<int, int>>> adj(n);
for (const auto& edge : edges) {
int u = edge[0], v = edge[1], w = edge[2];
adj[u].push_back({v, w}); // Normal edge
adj[v].push_back({u, 2 * w}); // Reversed edge option
}
// Dijkstra's algorithm using a priority queue
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
vector<long long> dist(n, LLONG_MAX);
dist[0] = 0;
pq.push({0, 0});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int weight = edge.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist[n - 1] == LLONG_MAX ? -1 : (int)dist[n - 1];
}
};
Python
import heapq
class Solution:
def minCost(self, n: int, edges: list[list[int]]) -> int:
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w)) # Normal edge
adj[v].append((u, 2 * w)) # Reversed edge option
# Priority queue stores (cost, current_node)
pq = [(0, 0)]
dist = [float('inf')] * n
dist[0] = 0
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > dist[u]:
continue
for v, weight in adj[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return int(dist[n - 1]) if dist[n - 1] != float('inf') else -1
JavaScript
/**
* @param {number} n
* @param {number[][]} edges
* @return {number}
*/
var minCost = function(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]); // Normal
adj[v].push([u, 2 * w]); // Reversed
}
const dist = new Array(n).fill(Infinity);
dist[0] = 0;
// Using a simple Min-Priority Queue structure
const pq = new MinPriorityQueue({ priority: x => x[0] });
pq.enqueue([0, 0]); // [cost, node]
while (!pq.isEmpty()) {
const [d, u] = pq.dequeue().element;
if (d > dist[u]) continue;
for (const [v, weight] of adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.enqueue([dist[v], v]);
}
}
}
return dist[n - 1] === Infinity ? -1 : dist[n - 1];
};
Key Takeaways
- Graph Augmentation: Sometimes, the best way to handle a "special move" is to represent it as a new type of edge in your graph.
- Dijkstra's Efficiency: When finding the shortest path in a graph with non-negative weights, Dijkstra's algorithm provides an efficient complexity of .
- State Simplification: By recognizing that the "reversal" is used immediately, we avoid complex DP states or tracking if a switch was used globally.
Final Thoughts
This problem is a classic example of how interviewers take a standard algorithm (Dijkstra) and add a "twist" to see if you can adapt. In real-world software engineering, this logic mirrors how routing engines work. For example, in a logistics system, a truck might usually take a highway, but under certain conditions, it might take a service road at a higher cost in fuel or time. Modeling these "conditional" paths is key to building robust navigation and optimization systems.
Top comments (0)