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