Connecting Cities With Minimum Cost

Problem Id: 1135 Difficulty: Medium


Intuition

Solution


class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        # Convert vertex index to be in [0, N]
        connections = [[i[0] - 1, i[1] - 1, i[2]] for i in connections]

        # Build the graph
        graph = WeightedGraph(N)
        for p, q, weight in connections:
            graph.add_edge(p, q, weight)

        # Minimum spanning tree
        path = 0
        visited = [False] * N
        heap = []
        for edge in graph.edges[0]:
            heapq.heappush(heap, edge)
        visited[0] = True

        while heap:
            edge = heapq.heappop(heap)
            one = edge.one()
            if visited[one]:
                one = edge.other(one)

            if visited[one]:
                continue
            visited[one] = True
            path += edge.weight
            for edge in graph.edges[one]:
                heapq.heappush(heap, edge)

        if not all(visited):
            return -1
        return path