Daily LeetCode - by Vítor Belim

Description

You are given a directed, weighted graph with n nodes labeled from 0 to n - 1, and an array edges where edges[i] = [u_i, v_i, w_i] represents a directed edge from node u_i to node v_i with cost w_i.

Each node u_i has a switch that can be used at most once: when you arrive at u_i and have not yet used its switch, you may activate it on one of its incoming edges v_i → u_i reverse that edge to u_i → v_i and immediately traverse it.

The reversal is only valid for that single move, and using a reversed edge costs 2 * w_i.

Return the minimum total cost to travel from node 0 to node n - 1. If it is 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:

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.

Constraints:

2 <= n <= 5 * 10⁴
1 <= edges.length <= 10⁵
edges[i] = [u_i, v_i, w_i]
0 <= u_i, v_i <= n - 1
1 <= w_i <= 1000

Solutions

This code uses Dijkstra's algorithm with a priority queue to find the shortest path from node 0 to node n-1 in a weighted graph. It builds an adjacency list g where each edge has a cost going one direction (weight w) and double that cost going the reverse direction (2*w). The algorithm maintains a dist array tracking the minimum distance to each node and processes nodes in order of their distance from the start. For each visited node, it checks all adjacent nodes and updates their distances if a shorter path is found, then enqueues them for processing. Once it reaches the destination node n-1, it returns the minimum cost found.

Language: javascript(2026-01-28 19:54)DONE

CPU Performance58.82%

Memory Performance41.18%

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var minCost = function (n, edges) {
    const g = Array.from({ length: n }, () => []);
    for (const e of edges) {
        const [x, y, w] = e;
        g[x].push([y, w]);
        g[y].push([x, 2 * w]);
    }

    const dist = Array(n).fill(Infinity);
    const visited = Array(n).fill(false);
    dist[0] = 0;
    const pq = new PriorityQueue((a, b) => {
        return a[0] < b[0] ? -1 : 1;
    });
    pq.enqueue([0, 0]);

    while (!pq.isEmpty()) {
        const [currentDist, x] = pq.dequeue();
        if (x === n - 1) {
            return currentDist;
        }

        if (visited[x]) {
            continue;
        }
        visited[x] = true;

        for (const [y, w] of g[x]) {
            if (currentDist + w < dist[y]) {
                dist[y] = currentDist + w;
                pq.enqueue([dist[y], y]);
            }
        }
    }

    return -1;
};

Description

Solutions

AI Explanation