Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Optimize Water Distribution in a Village (hard)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

There is a village with n houses connected by pipes. You need to ensure that each house will get a water supply.

For each house i, you can either dig a well inside it with cost wells[i - 1] or get water via a pipe from another well to it. The costs to get water via pipes between houses are given by the array pipes where each pipes[j] = [house1<sub>j</sub>, house2<sub>j</sub>, cost<sub>j</sub>] represents the cost to connect house1<sub>j</sub> and house2<sub>j</sub> together using a pipe. Here, pipe connection is bidirectonal.

Return the minimum total cost to supply water to all houses.

Examples

Example 1:

  • Input: n = 5, wells = [3, 2, 1, 4, 5], pipes = [[1, 2, 2], [2, 3, 3], [3, 4, 1], [4, 5, 2]]
  • Output: 8
  • Explanation: Dig wells for houses 3, and supply water to other houses from house 3.

Example 2:

  • Input: n = 4, wells = [1, 2, 2, 3], pipes = [[1, 2, 1], [2, 3, 1], [3, 4, 1]]
  • Expected Output: 4
  • Explanation: Dig wells for houses 1, and lay pipes between houses 1 and 2, houses 2 and 3, and houses 3 and 4.

Example 3:

  • Input: n = 3, wells = [2, 1, 2], pipes = [[1, 2, 2], [2, 3, 1]]
  • Output: 4
  • Explanation: Dig wells for houses 2, and lay a pipe between houses 2 and 3, and 1 and 2.

Constraints:

  • 2 <= n <= 10<sup>4</sup>
  • wells.length == n
  • 0 <= wells[i] <= 10<sup>4</sup>
  • 1 <= pipes.length <= 10<sup>4</sup>
  • pipes[j].length == 3
  • 1 <= house1<sub>j</sub>, house2<sub>j</sub> <= n
  • 0 <= cost<sub>j</sub> <= 10<sub>j</sub>
  • house1<sub>j</sub> != house2<sub>j</sub>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself