761. Wells and Pipes
A village has n houses numbered 0 to n - 1 and none has running water yet. For house i the council can drill a private well for wells[i] coins. It can also lay a two-way pipe between houses: each entry [a, b, cost] of pipes is an available pipe between houses a and b that costs cost coins.
A house has water if it has its own well or is joined by pipes to a house that has water. Return the minimum total number of coins needed so that every house has water. Pipes between the same pair of houses may be offered more than once with different prices.
Example 1
- Input:
- n = 3wells = [5,4,9]pipes = [[0,1,2],[1,2,3],[0,2,1]]
- Output:
- 7
- Explanation:
Dig one well at house 1 (cost 4) and lay pipes 0-2 (1), 0-1 (2): all three houses are supplied for 4 + 1 + 2 = 7.
Example 2
- Input:
- n = 3, wells = [1,1,1], pipes = [[0,1,5],[1,2,5]]
- Output:
- 3
- Explanation:
Pipes cost more than a well, so each house digs its own well: 1 + 1 + 1 = 3.
Example 3
- Input:
- n = 4wells = [10,10,10,1]pipes = [[0,3,1],[1,3,2],[2,3,3]]
- Output:
- 7
- Explanation:
One cheap well at house 3 (cost 1) feeds the other three through pipes costing 1, 2 and 3, for a total of 7.
Constraints
- 1 ≤ n ≤ 104
- wells.length == n and 0 ≤ wells[i] ≤ 105
- 0 ≤ pipes.length ≤ 3 * 104
- 0 ≤ a, b < n, a ≠ b, and 0 ≤ cost ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O((n + m) log (n + m))
- Space
- O(n + m)