3650. Minimum Cost Path with Edge Reversals

/**
 * Problem: LeetCode 3650 - Minimum Cost Path with Edge Reversals
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int minCost(int n, int[][] edges) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // Build augmented graph:
        // Original edge u -> v with cost w
        // Reversed edge v -> u with cost 2 * w (representing switch at v)
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, 2 * w});
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

        // Min-PriorityQueue storing {cost, node}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int u = curr[1];

            if (d > dist[u]) {
                continue;
            }

            if (u == n - 1) {
                return d;
            }

            for (int[] next : graph.get(u)) {
                int v = next[0];
                int weight = next[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }

        return dist[n - 1] == Integer.MAX_VALUE ? -1 : dist[n - 1];
    }
}

"""
Problem: LeetCode 3650 - Minimum Cost Path with Edge Reversals
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List
import heapq

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

        # Original directed edge u -> v with cost w
        # Reversed edge v -> u with cost 2 * w
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, 2 * w))

        dist = [float('inf')] * n
        dist[0] = 0
        min_heap = [(0, 0)]  # (cost, node)

        while min_heap:
            current_cost, u = heapq.heappop(min_heap)

            if current_cost > dist[u]:
                continue

            if u == n - 1:
                return current_cost

            for v, weight in graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(min_heap, (dist[v], v))

        return -1 if dist[n - 1] == float('inf') else dist[n - 1]

/**
 * Problem: LeetCode 3650 - Minimum Cost Path with Edge Reversals
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> graph(n);

        // Original directed edge u -> v with cost w
        // Reversed edge v -> u with cost 2 * w
        for (const auto& edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, 2 * w});
        }

        vector<int> dist(n, INT_MAX);
        dist[0] = 0;

        // Min-PriorityQueue: pair<cost, node>
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, 0});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            if (d > dist[u]) {
                continue;
            }

            if (u == n - 1) {
                return d;
            }

            for (const auto& [v, weight] : graph[u]) {
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }

        return dist[n - 1] == INT_MAX ? -1 : dist[n - 1];
    }
};

/**
 * Problem: LeetCode 3650 - Minimum Cost Path with Edge Reversals
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * Min-Heap implementation for Dijkstra
 */
class MinPriorityQueue {
    constructor() {
        this.heap = [];
    }

    push(item) {
        this.heap.push(item);
        this._siftUp();
    }

    pop() {
        if (this.isEmpty()) return null;
        const top = this.heap[0];
        const bottom = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this._siftDown();
        }
        return top;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    _siftUp() {
        let nodeIdx = this.heap.length - 1;
        while (nodeIdx > 0) {
            const parentIdx = (nodeIdx - 1) >> 1;
            if (this.heap[nodeIdx][0] < this.heap[parentIdx][0]) {
                [this.heap[nodeIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[nodeIdx]];
                nodeIdx = parentIdx;
            } else {
                break;
            }
        }
    }

    _siftDown() {
        let nodeIdx = 0;
        const length = this.heap.length;
        while ((nodeIdx << 1) + 1 < length) {
            let smallerChildIdx = (nodeIdx << 1) + 1;
            const rightChildIdx = smallerChildIdx + 1;
            if (rightChildIdx < length && this.heap[rightChildIdx][0] < this.heap[smallerChildIdx][0]) {
                smallerChildIdx = rightChildIdx;
            }
            if (this.heap[smallerChildIdx][0] < this.heap[nodeIdx][0]) {
                [this.heap[nodeIdx], this.heap[smallerChildIdx]] = [this.heap[smallerChildIdx], this.heap[nodeIdx]];
                nodeIdx = smallerChildIdx;
            } else {
                break;
            }
        }
    }
}

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var minCost = function(n, edges) {
    const graph = Array.from({ length: n }, () => []);

    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, 2 * w]);
    }

    const dist = new Array(n).fill(Infinity);
    dist[0] = 0;

    const pq = new MinPriorityQueue();
    pq.push([0, 0]); // [cost, node]

    while (!pq.isEmpty()) {
        const [d, u] = pq.pop();

        if (d > dist[u]) continue;
        if (u === n - 1) return d;

        for (const [v, weight] of graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push([dist[v], v]);
            }
        }
    }

    return dist[n - 1] === Infinity ? -1 : dist[n - 1];
};