There are N homes in a village, we have to facilitate water supply in each of them. We can either build a well in a home or connect it with pipe to some different home already having water supply. More formally, we can either build a new well in the home or connect it with a pipeline to some different home which either has it’s own well or further gets water supply from a different home and so on. There is some cost associated with both building a new well and laying down a new pipeline. We have to supply water in all homes and minimise the total cost.
First line contains an integer N, the number of homes.
The next line contains N integers, the ith integer denotes the cost of building a well in that home.
Next line contains an integer K, then K lines follows. Each of which contains 3 integers i, j and p. Which denotes the cost ‘p’ of laying down pipeline between homes i and j.
Output a single integer - the minimum cost to supply water to all the homes
Link to the problem- https://leetcode.com/problems/optimize-water-distribution-in-a-village/
Unfortunately, Leetcode has moved the problem to ‘for premium users only’ since the last time I tried it. So, you won’t be able to access it unless you have the premium subscription. But fortunately, I remember the problem statement.