3650. Minimum Cost Path with Edge Reversals Medium

1/**
2 * [3650] Minimum Cost Path with Edge Reversals
3 *
4 * 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 to node vi with cost wi.
5 * Each node ui has a switch that can be used at most once: when you arrive at ui and have not yet used its switch, you may activate it on one of its incoming edges vi → ui reverse that edge to ui → vi and immediately traverse it.
6 * The reversal is only valid for that single move, and using a reversed edge costs 2 * wi.
7 * Return the minimum total cost to travel from node 0 to node n - 1. If it is not possible, return -1.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]</span>
12 * Output: <span class="example-io">5</span>
13 * Explanation: 
14 * <img alt="" src="https://assets.leetcode.com/uploads/2025/05/07/e1drawio.png" style="width: 171px; height: 111px;" />
15 * 
16 * 	Use the path 0 &rarr; 1 (cost 3).
17 * 	At node 1 reverse the original edge 3 &rarr; 1 into 1 &rarr; 3 and traverse it at cost 2 * 1 = 2.
18 * 	Total cost is 3 + 2 = 5.
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]</span>
23 * Output: <span class="example-io">3</span>
24 * Explanation:
25 * 
26 * 	No reversal is needed. Take the path 0 &rarr; 2 (cost 1), then 2 &rarr; 1 (cost 1), then 1 &rarr; 3 (cost 1).
27 * 	Total cost is 1 + 1 + 1 = 3.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n <= 5 * 10^4
33 * 	1 <= edges.length <= 10^5
34 * 	edges[i] = [ui, vi, wi]
35 * 	0 <= ui, vi <= n - 1
36 * 	1 <= wi <= 1000
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/minimum-cost-path-with-edge-reversals/
42// discuss: https://leetcode.com/problems/minimum-cost-path-with-edge-reversals/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn min_cost(n: i32, edges: Vec<Vec<i32>>) -> i32 {
48        0
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_3650() {
60    }
61}
62