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_j, house2_j, cost_j] represents the cost to connect house1_j and house2_j 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⁴
• wells.length == n
• 0 <= wells[i] <= 10⁴
• 1 <= pipes.length <= 10⁴
• pipes[j].length == 3
• 1 <= house1_j, house2_j <= n
• 0 <= cost_j <= 10_j
• house1_j != house2_j

Solution

To solve this problem, we'll use Prim's algorithm, a well-known method for finding the Minimum Spanning Tree (MST) in a graph. The MST helps us connect all houses with the least total cost. We treat each house and the costs of wells as separate nodes, and the pipes as edges between nodes. By initially considering the costs of wells as edges connecting each house to a virtual node, we can include them in our MST calculation.

This approach ensures that we account for both digging wells and laying pipes efficiently. Prim's algorithm is effective here because it incrementally builds the MST by adding the cheapest edge from the existing tree to a new node, ensuring minimal costs at each step.

Step-by-Step Algorithm

1. Initialize the Priority Queue:

   • Create a priority queue edgesHeap to store the edges based on their costs.

2. Graph Representation:

   • Create an adjacency list graph to represent the graph. The graph will have n + 1 nodes (including the virtual node 0).

3. Add Virtual Edges:

   • For each well, create an edge from the virtual node 0 to each house with the cost of the well. Add these edges to both the graph and the priority queue.

4. Add Bidirectional Edges:

   • For each pipe, create bidirectional edges between the two houses and add these edges to the graph.

5. Initialize MST Set:

   • Create a set mstSet to track the houses included in the minimum spanning tree (MST). Start by adding the virtual node 0 to the set.

6. Total Cost Initialization:

   • Initialize totalCost to 0 to keep track of the total cost of supplying water to all houses.

7. Process Edges in Priority Queue:

   • While the number of houses in mstSet is less than n + 1:
     • Extract the edge with the minimum cost from the priority queue.
     • If the house connected by this edge is already in mstSet, skip this edge.
     • Otherwise, add the house to mstSet and add the cost of the edge to totalCost.
     • Add all edges connected to this house to the priority queue if the connected house is not already in mstSet.

8. Return Total Cost:

   • Return the totalCost as the result.

Algorithm Walkthrough

Given:

• n = 5
• wells = [3, 2, 1, 4, 5]
• pipes = [[1, 2, 2], [2, 3, 3], [3, 4, 1], [4, 5, 2]]

Step-by-Step Execution:

1. Initialize the Priority Queue:

   • Priority queue edgesHeap is created.

2. Graph Representation:

   • Adjacency list graph with 6 nodes (0 to 5) is created.

3. Add Virtual Edges:

   • Edges from node 0 to each house are added:
     • (3, 1) for house 1
     • (2, 2) for house 2
     • (1, 3) for house 3
     • (4, 4) for house 4
     • (5, 5) for house 5
   • These edges are also added to the priority queue.

4. Add Bidirectional Edges:

   • Edges between houses are added to the graph:
     • (2, 2) and (2, 1) between house 1 and house 2
     • (3, 3) and (3, 2) between house 2 and house 3
     • (1, 4) and (1, 3) between house 3 and house 4
     • (2, 5) and (2, 4) between house 4 and house 5

5. Initialize MST Set:

   • Set mstSet is initialized with node 0.

6. Total Cost Initialization:

   • totalCost is initialized to 0.

7. Process Edges in Priority Queue:

   • Iteration 1:
     • Extract edge (1, 3) from priority queue.
     • Add house 3 to mstSet and add 1 to totalCost (totalCost = 1).
     • Add edges (1, 4) and (3, 2) connected to house 3 to the priority queue.
   • Iteration 2:
     • Extract edge (2, 2) from priority queue.
     • Add house 2 to mstSet and add 2 to totalCost (totalCost = 3).
     • Add edges (2, 1) and (3, 3) connected to house 2 to the priority queue.
   • Iteration 3:
     • Extract edge (1, 4) from priority queue.
     • Add house 4 to mstSet and add 1 to totalCost (totalCost = 4).
     • Add edge (2, 5) connected to house 4 to the priority queue.
   • Iteration 4:
     • Extract edge (2, 1) from priority queue.
     • Add house 1 to mstSet and add 2 to totalCost (totalCost = 6).
     • No new edges to add since house 2 is already in mstSet.
   • Iteration 5:
     • Extract edge (2, 5) from priority queue.
     • Add house 5 to mstSet and add 2 to totalCost (totalCost = 8).
     • No new edges to add since house 4 is already in mstSet.

8. Return Total Cost:

   • Return totalCost which is 8.

Code