There are n houses, and each house can either build its own well or receive water through pipes from another house. You are given the well-building cost for each house and a list of bidirectional pipes with construction costs. Return the minimum cost to supply water to every house. Pattern focus: MST. Model the virtual water source as a node and connect it to each house with its well cost.
n = number of houses, wells = cost to build a well in each house, pipes = list of pipe connections [house1, house2, cost]
minimum total cost to supply water to every house
Example 1:
Input:
n = 3 wells = [1,2,2] pipes = [[1,2,1],[2,3,1]]
Output:
3
Explanation:
Build one well at house 1 and use two cheap pipes to supply all houses.
Example 2:
Input:
n = 2 wells = [5,1] pipes = []
Output:
6
Explanation:
The cheapest choice is to build both wells.
Example 3:
Input:
n = 4 wells = [5,5,5,5] pipes = [[1,2,1],[2,3,1],[3,4,1]]
Output:
8
Explanation:
One well plus three pipes gives the minimum total cost.