Minimum Cost Path with Edge Reversals — Algorithm Visualization & Coding Challenge

Minimum Cost Path with Edge Reversals

Difficulty: Medium

🧩 Problem Statement

You are given a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where:

edges[i] = [ui, vi, wi]

represents a directed edge from node ui → vi with cost wi.

🔁 Special Rule (Edge Reversal)

• Each node ui has a switch that can be used at most once.
• When you arrive at ui and haven't used its switch:
  • You may pick one incoming edge vi → ui
  • Reverse it to ui → vi
  • Immediately traverse it
• This reversed traversal costs 2 × wi
• The reversal is valid only for that single move

🎯 Goal

Return the minimum total cost to travel from node 0 to node n - 1.
If it’s not possible, return -1.

📌 Example 1

Input

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

Output

5

Explanation

• 0 → 1 (cost 3)
• At node 1, reverse edge 3 → 1 to 1 → 3 and traverse (cost 2 × 1 = 2)
• Total cost = 5

📌 Example 2

Input

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

Output

3

Explanation

• 0 → 2 → 1 → 3
• No reversal needed
• Total cost = 3

⚙️ Constraints

• 2 ≤ n ≤ 5 × 10⁴
• 1 ≤ edges.length ≤ 10⁵
• 0 ≤ ui, vi < n
• 1 ≤ wi ≤ 1000