题解 | 最小生成树

from io import RawIOBase
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回最小的花费代价使得这n户人家连接起来
# @param n int整型 n户人家的村庄
# @param m int整型 m条路
# @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int整型
#
import heapq
class Solution:
    def miniSpanningTree(self , n: int, m: int, cost: List[List[int]]) -> int:
        # write code here
        h = []
        vis = [0 for i in range(n + 1)]
        res = 0
        road = [[]for i in range(n+ 1)]
        for c in cost:
            x, y, z = c[0], c[1], c[2]
            road[x].append([y, z])
            road[y].append([x, z])
        heapq.heappush(h, (0, [1, 1]))

        while h:
            w, t = heapq.heappop(h)
            x, y = t[0], t[1]
            if vis[x] + vis[y] == 2:
                continue
            vis[x] = 1
            vis[y] = 1
            res += w
            for r in road[y]:
                yy, w = r[0], r[1]
                if vis[yy] == 1: continue
                heapq.heappush(h, (w, [y, yy]))
        return res

prim算法，注意这个图是无向边，要记录两个方向的，我忘了这个搞得错误回答了几次，x能去y，那么y也能去x，如下代码

road[x].append([y, z])

road[y].append([x, z])