Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each original edge offers a forward move at its weight and a one-move reversed traversal at twice that weight. Although each node's switch can be used only once, positive costs allow a shortest path to be simple, visiting each node only once. No switch-history state is needed.

Approach

For every edge u -> v of cost w, add a forward adjacency entry of cost w and a reverse entry of cost 2 * w. Initialize node zero's distance to zero and every other distance to infinity.

Use a min-heap to remove queued distances and relax outgoing edges, enqueueing every strict improvement. JavaScript skips an entry whose distance is outdated and returns when the destination is removed with its current distance. Python scans outgoing edges even for outdated entries and empties the heap before returning the stored destination distance. These stale scans cannot improve a neighbor because the smaller current distance was processed earlier, but they add work. Return -1 if the destination is unreachable.

The augmented graph includes every legal individual move. Conversely, deleting cycles lowers a route's positive cost and leaves a simple route that cannot reuse a node's switch. Thus the graph model preserves the optimal legal answer.

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        adj = defaultdict(list)

        for a, b, w in edges:
            adj[a].append((b, w))
            adj[b].append((a, w * 2))

        dist = [0] + [inf] * (n - 1)
        heap = []
        heapq.heappush(heap, (0, 0)) # w, node

        while heap:
            w, node = heapq.heappop(heap)
            for nei, nw in adj[node]:
                if w + nw < dist[nei]:
                    dist[nei] = w + nw
                    heapq.heappush(heap, (w + nw, nei))

        return dist[n - 1] if dist[n - 1] != inf else -1

Complexity analysis

Let N be the node count and E the original edge count; the augmented graph has 2E edges, including any duplicates. JavaScript skips stale heap entries, giving O(N + Elog(E+1)) time. Python does not: there are O(E) queued improvements, each stale pop may rescan up to O(E) outgoing edges, giving the conservative O(N + E^2 + Elog(E+1)) time bound. Both use O(N+E) auxiliary space for graph, distances and a heap that may contain multiple entries per vertex. Positive weights ensure stale scans cannot create further improvements.