Asked at

Optimize Water Distribution In A Village

Hard
VerifiedMSTUnion FindGreedy~35 min

You have n houses labeled 1..n. Supplying water to a house costs either wells[i - 1] to build a well at house i, or the pipe cost to route water from a neighbor. Each pipe in pipes is [house1, house2, cost].

Return the minimum total cost to supply water to every house. Hint: add a virtual node 0 and turn each well into an edge [0, i, wells[i - 1]], then run an MST.

The input arrives as a single object { n, wells, pipes }.

Examples

in{ n: 3, wells: [1,2,2], pipes: [[1,2,1],[2,3,1]] }
out3

Build a well at house 1 (cost 1), then pipe to houses 2 and 3 (cost 1 each).

in{ n: 2, wells: [1,1], pipes: [[1,2,1]] }
out2

Build a well at each house for total cost 2; the pipe is not cheaper.

Constraints

  • 1 ≤ n ≤ 10⁴
  • wells.length == n
  • 0 ≤ wells[i] ≤ 10⁵
  • pipes[j] = [house1, house2, cost], houses labeled 1..n
  • 0 ≤ cost ≤ 10⁵

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.