本文共 1435 字，大约阅读时间需要 4 分钟。

题目：（中等）

标签：图、Prim算法、Kruskal算法

解法一：

class Solution:    def minimumCost(self, n: int, connections: List[List[int]]) -> int:        min_idx, min_val = (-1, -1), float("inf")        graph = collections.defaultdict(dict)        for edge in connections:            if edge[1] not in graph[edge[0]] or edge[2] < graph[edge[0]][edge[1]]:                graph[edge[0]][edge[1]] = edge[2]                graph[edge[1]][edge[0]] = edge[2]                if edge[2] < min_val:                    min_idx, min_val = (edge[0], edge[1]), edge[2]        ans = 0        waiting = {
   i for i in range(1, n + 1)}        heap = []        # 添加最短的边        ans += min_val        waiting.remove(min_idx[0])        waiting.remove(min_idx[1])        for n2, v2 in graph[min_idx[0]].items():            if n2 in waiting:                heapq.heappush(heap, (v2, n2))        for n2, v2 in graph[min_idx[1]].items():            if n2 in waiting:                heapq.heappush(heap, (v2, n2))        while heap and waiting:            v1, n1 = heapq.heappop(heap)            if n1 in waiting:                ans += v1                waiting.remove(n1)                for n2, v2 in graph[n1].items():                    if n2 in waiting:                        heapq.heappush(heap, (v2, n2))        return ans if not waiting else -1

转载地址：http://jxkcf.baihongyu.com/