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

题目：（困难）

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

解法一：

import collectionsimport heapqfrom typing import Listclass Solution:    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:        graph = collections.defaultdict(dict)        for edge in pipes:            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]        # 添加所有房屋到地下水结点的距离        for i, well in enumerate(wells):            graph[0][i + 1] = well        ans = 0        waiting = {
   i for i in range(0, n + 1)}        heap = [(0, 0)]        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

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