house_count houses numbered 1 to house_count, and every one of them needs water. There are two ways to get it:
- dig a well right in house i, which costs well_cost[i - 1];
- run a pipe from a house that already has water. The entry pipes[j] = [a, b, cost] says houses a and b can be linked with a pipe for cost; water flows both ways. The same pair of houses may appear several times with different prices.
Return the lowest total cost that gets water into every house.house_count=3, well_cost=[5, 1, 4], pipes=[[1, 2, 2], [2, 3, 6]] → 7
A well in house 2 for 1 and a pipe 1–2 for 2. For house 3 its own well (4) is cheaper than the pipe (6). Total 1 + 2 + 4 = 7.
house_count=2, well_cost=[0, 0], pipes=[[1, 2, 3]] → 0
Wells are free, so no pipes are needed.
house_count=4, well_cost=[9, 9, 2, 9], pipes=[[1, 2, 1], [2, 3, 3], [3, 4, 1], [1, 4, 5]] → 7
house_count ≤ 10⁴well_cost) = house_countwell_cost[i] ≤ 10⁵pipes) ≤ 10⁴a, b ≤ house_count, a ≠ bcost ≤ 10⁵house_count=3, well_cost=[5, 1, 4], pipes=[[1, 2, 2], [2, 3, 6]]
7
Run checks the first 3 tests in your browser. Submit checks all 76 tests on the server, hidden ones included.