Leetcode 1100 Solution

This article provides solution to leetcode question 1100 (connecting-cities-with-minimum-cost)
Categories:
Tags:
Access this page by simply typing in "lcs 1100" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/connecting-cities-with-minimum-cost

Solution

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        graph = collections.defaultdict(list)

        for src, dst, cost in connections:
            graph[src].append((dst, cost))
            graph[dst].append((src, cost))

        nodes = {1}
        q = []
        for dst, cost in graph.get(1, []):
            heapq.heappush(q, (cost, dst))

        ans = 0
        while len(nodes) < n:
            found = False
            while q:
                cost, dst = heapq.heappop(q)
                if dst not in nodes:
                    ans += cost

                    nodes.add(dst)
                    for dst_neigh, cost in graph.get(dst, []):
                        heapq.heappush(q, (cost, dst_neigh))

                    found = True

            if found == False:
                return -1

        return ans