题解 | #最小生成树#

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

        for k in range(1, n-1):
            for c in cost:
                if ((visit[c[0]] == 1 and visit[c[1]] == 0) or (visit[c[0]] == 0 and visit[c[1]] == 1)):
                    cost_sum += c[2]
                    visit[c[0]] = 1
                    visit[c[1]] = 1
                    cost.remove(c)
                    break

        return cost_sum