Problem Statement in English

You’re given an integer n representing the number of nodes in a directed graph, numbered from 0 to n - 1. You’re also given a 2D integer array edges, where each edges[i]=[ui,vi,wi]edges[i] = [u_i, v_i, w_i] indicates a directed edge from node uiu_i to node viv_i with a cost of wiw_i.

You can reverse the direction of any edge at a cost of twice its original weight. Your task is to find the minimum cost required to travel from node 0 to node n - 1.

You cannot reverse an edge more than once.

Approach

This is honestly such a scam. It’s just trying to throw you off by adding the edge reversal cost.

But in reality, we can just treat the edge reversal as a different edge with a different cost. There’s no reason why you’ll ever come back to a node and want to reverse the edge again, if you’ve already reversed it once.

So basically just build a graph where for each edge u→vu \to v with weight ww, you also add an edge v→uv \to u with weight 2w2w. Then just run Dijkstra’s algorithm to find the minimum cost path from node 0 to node n - 1.

The laws of Dijkstra’s algorithm still hold because all edge weights are non-negative.

Solution in Python


class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        minheap = [(0, 0)] # val, node at

        adjList = defaultdict(list)

        for u, v, w in edges:
            adjList[u].append((v, w))
            adjList[v].append((u, 2 * w))

        seen = set()

        while minheap:
            val, node = heappop(minheap)

            if node == n - 1:
                return val

            if node in seen:
                continue
            seen.add(node)

            for nei, w in adjList[node]:
                heappush(minheap, (val + w, nei))

        return -1

Complexity

  • Time: O(nlog⁡n)O(n \log n)
    Since we are using a min-heap to explore the nodes based on the minimum cost, each node and edge will be processed in logarithmic time relative to the number of nodes.

  • Space: O(n)O(n)
    We use an adjacency list to store the graph, which takes up space proportional to the number of nodes and edges. The min-heap also requires space proportional to the number of nodes in the worst case.

And we are done.