1584. Min Cost to Connect All Points

• exactly prim algorithms

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        N = len(points)

        adj = defaultdict(list)

        for i in range(N):
            x1, y1 = points[i]
            for j in range(i + 1, N):
                x2, y2 = points[j]
                dist = abs(x1 - x2) + abs(y1 - y2)
                adj[i].append([dist, j])
                adj[j].append([dist, i])


        res = 0
        visited = set()
        minH = [[0, 0]]

        while len(visited) < N:
            cost, i = heapq.heappop(minH)

            if i in visited:
                continue
            res += cost
            visited.add(i)
            for neiCost, j in adj[i]:
                if j not in visited:
                    heapq.heappush(minH, [neiCost, j])


        return res