Village Wells
Hard · minimum spanning tree
There are n villages, numbered 1 to n, and every one of them needs running water.
A village gets water in one of two ways:
- it digs its own well, which costs
wells[i - 1]for villagei, or - it is joined by laid pipes, directly or through other villages, to a village that has water.
The list pipes holds the pipes you are allowed to lay. Each entry is [a, b, cost]: a pipe between villages a and b that costs cost to lay and carries water in both directions. You may lay any of them, in any combination, and pipes you do not lay cost nothing.
Return the smallest total cost (wells dug plus pipes laid) so that every village has water.
Several pipes may join the same two villages, with different costs. Costs may be 0.
Examples
Example 1
Input: n = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]]
Output: 3
Dig one well in village 1 (cost 1), then lay the pipes 1-2 and 2-3 (cost 1 each): 1 + 1 + 1 = 3.
Example 2
Input: n = 2, wells = [4, 4], pipes = [[1, 2, 5]]
Output: 8
The pipe costs more than a well, so each village digs its own: 4 + 4 = 8.
Example 3
Input: n = 1, wells = [7], pipes = []
Output: 7
The only village must dig its own well.
Constraints
- 1 <= n <= 1000
- len(wells) == n and 0 <= wells[i] <= 10^5
- 0 <= len(pipes) <= 10^4
- Each pipe is [a, b, cost] with 1 <= a, b <= n, a != b and 0 <= cost <= 10^5.