代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.
For each house i, we can either build a well inside it directly with cost wells[i - 1] (note the -1 due to 0-indexing), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes where each pipes[j] = [house1j, house2j, costj] represents the cost to connect house1j and house2j together using a pipe. Connections are bidirectional, and there could be multiple valid connections between the same two houses with different costs.
Return the minimum total cost to supply water to all houses.
Example 1:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] Output: 3 Explanation: The image shows the costs of connecting houses using pipes. The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
Example 2:
Input: n = 2, wells = [1,1], pipes = [[1,2,1],[1,2,2]] Output: 2 Explanation: We can supply water with cost two using one of the three options: Option 1: - Build a well inside house 1 with cost 1. - Build a well inside house 2 with cost 1. The total cost will be 2. Option 2: - Build a well inside house 1 with cost 1. - Connect house 2 with house 1 with cost 1. The total cost will be 2. Option 3: - Build a well inside house 2 with cost 1. - Connect house 1 with house 2 with cost 1. The total cost will be 2. Note that we can connect houses 1 and 2 with cost 1 or with cost 2 but we will always choose the cheapest option.
Constraints:
2 <= n <= 104wells.length == n0 <= wells[i] <= 1051 <= pipes.length <= 104pipes[j].length == 31 <= house1j, house2j <= n0 <= costj <= 105house1j != house2jUnion find.
class Solution:
def minCostToSupplyWater(
self, n: int, wells: List[int], pipes: List[List[int]]
) -> int:
for i, w in enumerate(wells):
pipes.append([0, i + 1, w])
pipes.sort(key=lambda x: x[2])
p = list(range(n + 1))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
res = 0
for u, v, w in pipes:
if find(u) == find(v):
continue
p[find(u)] = find(v)
res += w
n -= 1
if n == 0:
break
return res
class Solution {
private int[] p;
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
int[][] all = new int[pipes.length + n][3];
int idx = 0;
for (int[] pipe : pipes) {
all[idx++] = pipe;
}
for (int j = 0; j < n; ++j) {
all[idx++] = new int[] {0, j + 1, wells[j]};
}
p = new int[n + 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
Arrays.sort(all, Comparator.comparingInt(a -> a[2]));
int res = 0;
for (int[] e : all) {
if (find(e[0]) == find(e[1])) {
continue;
}
p[find(e[0])] = find(e[1]);
res += e[2];
--n;
if (n == 0) {
break;
}
}
return res;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
class Solution {
public:
vector<int> p;
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
p.resize(n + 1);
for (int i = 0; i < p.size(); ++i) p[i] = i;
for (int i = 0; i < n; ++i) pipes.push_back({0, i + 1, wells[i]});
sort(pipes.begin(), pipes.end(), [](const auto& a, const auto& b) {
return a[2] < b[2];
});
int res = 0;
for (auto e : pipes) {
if (find(e[0]) == find(e[1])) continue;
p[find(e[0])] = find(e[1]);
res += e[2];
--n;
if (n == 0) break;
}
return res;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};
var p []int
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
p = make([]int, n+1)
for i := 0; i < len(p); i++ {
p[i] = i
}
for i, w := range wells {
pipes = append(pipes, []int{0, i + 1, w})
}
sort.Slice(pipes, func(i, j int) bool {
return pipes[i][2] < pipes[j][2]
})
res := 0
for _, e := range pipes {
if find(e[0]) == find(e[1]) {
continue
}
p[find(e[0])] = find(e[1])
res += e[2]
n--
if n == 0 {
break
}
}
return res
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
