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

想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。

给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。

返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。

示例 1：

输入：N = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]输出：6解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。

示例 2：

输入：N = 4, conections = [[1,2,3],[3,4,4]]输出：-1解释： 即使连通所有的边，也无法连接所有城市。

提示：

1. 1 <= N <= 10000
2. 1 <= conections.length <= 10000
3. 1 <= conections[i][0], conections[i][1] <= N
4. 0 <= conections[i][2] <= 10^5
5. conections[i][0] != conections[i][1]

解题思路

这是最小生成树问题，我们可以使用Kruskal算法， 参看。我们直接将文末的代码稍加修改即可

class Solution:    def minimumCost(self, N: int, connections: List[List[int]]) -> int:          if len(connections) < N - 1:            return -1        connections.sort(key=lambda a : a[2])        parent = [i for i in range(N)]                def find(x):            if x != parent[x]:                parent[x] = find(parent[x])            return parent[x]                res, e, k = 0, 0, 0        while e < N - 1:            u, v, w = connections[k]            k += 1            x, y = find(u-1), find(v-1)            if x != y:                e += 1                res += w                parent[x] = y        return res

对于无法连接所有城市的情况我们只需要通过通过判断connections中边的数目是不是比最小生成树中点的数目N-1少即可。

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/97617160 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！