汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

最小生成树

描述
一个有 n 户人家的村庄,有 m 条路相互连接着。村里现在要修路,每条路都有一个成本价格,现在请你帮忙计算下,最少需要花费多少钱,就能让这 n 户人家连接起来。

cost为一个二维数组,每个元素是一个长度为3的一维数组 a ,a[0]和a[1]表示村庄a[0]和村庄a[1]有一条路,修这条路的成本价格为 a[2] .

每户之间可能有多条道路连接,但不可能自己与自己相连

进阶: 时间复杂度 O(n+mlogm), 空间复杂度 O(n)

示例1
输入:
3,3,[[1,3,3],[1,2,1],[2,3,1]]
返回值:
2

示例2
输入:
2,1,[[1,2,1]]
返回值:
1


坚持原创分享,您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------