`{"id":"0d524ce6-a4b5-402c-9b92-3609d3672aa3","name":"Optimize Water Distribution","description":"There are n construction sites in a town. We want to supply water for all the construction sites by building wells and laying pipes.\r\n\r\nFor each site i, we can either build a well inside it directly with cost wells[i-1], or pipe in water from another well to it. The costs to lay pipes between\r\nsites are given by the 2d array cost, where each row of cost contains 3 numbers ai,bi and wi where wi is the cost to connect ai to bi. connections are bidirectional.\r\n\r\nReturn the minimum total cost to supply water to all the construction sites.\r\n","inputFormat":"First line contains two integers V and E denoting number of houses and number of pipelines respectively.\r\nSecond line contains n integer denoting cost to dig well at ith house.\r\nEach of next E lines contain 3 numbers ui and vi and c denoting a pipeline between u and v with cost c to build.","outputFormat":"Return the minimum total cost to supply water to all the construction sites.","constraints":"1 &lt;= n &lt;= 10^4\r\nwells.length == n\r\n0 &lt;= wells[i] &lt;= 10^5\r\n1 &lt;= cost.length &lt;= 10^4\r\ncost[i].length == 3","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint minCostToSupplyWater(int n, vector<int>&wells, vector<vector<int>>& pipes){\n//write your code here\n}\n\n\nint main(){\n int v,e;\n cin>>v>>e;\n \n \n vector<int>wells(v);\n \n for(int i=0;i<v;i++){\n cin>>wells[i];\n }\n \n \n vector<vector<int>>pipes(e,vector<int>(3));\n \n for(int i=0;i<e;i++){\n for(int j=0;j<3;j++){\n cin>>pipes[i][j];\n }\n }\n \n cout<<minCostToSupplyWater(v, wells, pipes);\n \n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\nclass Main {\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int v = Integer.parseInt(st[0]);\n int e = Integer.parseInt(st[1]);\n\n int[] wells = new int[v];\n String[] words = br.readLine().split(\" \");\n\n for (int i = 0; i < wells.length; i++) {\n wells[i] = Integer.parseInt(words[i]);\n }\n\n int[][] pipes = new int[e][3];\n for (int i = 0; i < e; i++) {\n String[] st1 = br.readLine().split(\" \");\n pipes[i][0] = Integer.parseInt(st1[0]);\n pipes[i][1] = Integer.parseInt(st1[1]);\n pipes[i][2] = Integer.parseInt(st1[2]);\n\n }\n\n System.out.println(minCostToSupplyWater(v, wells, pipes));\n\n }\n\n public static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {\n\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 2\r\n1 2 2\r\n1 2 1\r\n2 3 1\r\n\r\n","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"d5b82b0c-2f99-4caf-ad77-1071418655ac","name":"Optimize Water Distribution","slug":"optimize-water-distribution","type":1}],"next":{"id":"12998d25-5a66-462b-853f-781e55275969","name":"Optimize water distribution hard MCQ","type":0,"slug":"optimize-water-distribution-hard-mcq"},"prev":{"id":"8279ac08-46eb-4d68-b2ca-a61f600cdd2d","name":"Prims vs Dijiktras","type":3,"slug":"prims-vs-dijiktras"}}}`

# Optimize Water Distribution

There are n construction sites in a town. We want to supply water for all the construction sites by building wells and laying pipes. For each site i, we can either build a well inside it directly with cost wells[i-1], or pipe in water from another well to it. The costs to lay pipes between sites are given by the 2d array cost, where each row of cost contains 3 numbers ai,bi and wi where wi is the cost to connect ai to bi. connections are bidirectional. Return the minimum total cost to supply water to all the construction sites.

`{"id":"0d524ce6-a4b5-402c-9b92-3609d3672aa3","name":"Optimize Water Distribution","description":"There are n construction sites in a town. We want to supply water for all the construction sites by building wells and laying pipes.\r\n\r\nFor each site i, we can either build a well inside it directly with cost wells[i-1], or pipe in water from another well to it. The costs to lay pipes between\r\nsites are given by the 2d array cost, where each row of cost contains 3 numbers ai,bi and wi where wi is the cost to connect ai to bi. connections are bidirectional.\r\n\r\nReturn the minimum total cost to supply water to all the construction sites.\r\n","inputFormat":"First line contains two integers V and E denoting number of houses and number of pipelines respectively.\r\nSecond line contains n integer denoting cost to dig well at ith house.\r\nEach of next E lines contain 3 numbers ui and vi and c denoting a pipeline between u and v with cost c to build.","outputFormat":"Return the minimum total cost to supply water to all the construction sites.","constraints":"1 &lt;= n &lt;= 10^4\r\nwells.length == n\r\n0 &lt;= wells[i] &lt;= 10^5\r\n1 &lt;= cost.length &lt;= 10^4\r\ncost[i].length == 3","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nint minCostToSupplyWater(int n, vector<int>&wells, vector<vector<int>>& pipes){\n//write your code here\n}\n\n\nint main(){\n int v,e;\n cin>>v>>e;\n \n \n vector<int>wells(v);\n \n for(int i=0;i<v;i++){\n cin>>wells[i];\n }\n \n \n vector<vector<int>>pipes(e,vector<int>(3));\n \n for(int i=0;i<e;i++){\n for(int j=0;j<3;j++){\n cin>>pipes[i][j];\n }\n }\n \n cout<<minCostToSupplyWater(v, wells, pipes);\n \n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\nclass Main {\n public static void main(String[] args) throws NumberFormatException, IOException {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n String[] st = br.readLine().split(\" \");\n int v = Integer.parseInt(st[0]);\n int e = Integer.parseInt(st[1]);\n\n int[] wells = new int[v];\n String[] words = br.readLine().split(\" \");\n\n for (int i = 0; i < wells.length; i++) {\n wells[i] = Integer.parseInt(words[i]);\n }\n\n int[][] pipes = new int[e][3];\n for (int i = 0; i < e; i++) {\n String[] st1 = br.readLine().split(\" \");\n pipes[i][0] = Integer.parseInt(st1[0]);\n pipes[i][1] = Integer.parseInt(st1[1]);\n pipes[i][2] = Integer.parseInt(st1[2]);\n\n }\n\n System.out.println(minCostToSupplyWater(v, wells, pipes));\n\n }\n\n public static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {\n\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"3 2\r\n1 2 2\r\n1 2 1\r\n2 3 1\r\n\r\n","sampleOutput":"3\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"7e07fddf-83bd-421e-848f-118f1f29541c","name":"Graphs For Intermediate","slug":"graphs-for-intermediate-493","type":0},{"id":"d5b82b0c-2f99-4caf-ad77-1071418655ac","name":"Optimize Water Distribution","slug":"optimize-water-distribution","type":1}],"next":{"id":"12998d25-5a66-462b-853f-781e55275969","name":"Optimize water distribution hard MCQ","type":0,"slug":"optimize-water-distribution-hard-mcq"},"prev":{"id":"8279ac08-46eb-4d68-b2ca-a61f600cdd2d","name":"Prims vs Dijiktras","type":3,"slug":"prims-vs-dijiktras"}}}`

Editor

# Optimize Water Distribution

easy

There are n construction sites in a town. We want to supply water for all the construction sites by building wells and laying pipes. For each site i, we can either build a well inside it directly with cost wells[i-1], or pipe in water from another well to it. The costs to lay pipes between sites are given by the 2d array cost, where each row of cost contains 3 numbers ai,bi and wi where wi is the cost to connect ai to bi. connections are bidirectional. Return the minimum total cost to supply water to all the construction sites.

## Constraints

1 <= n <= 10^4 wells.length == n 0 <= wells[i] <= 10^5 1 <= cost.length <= 10^4 cost[i].length == 3

## Format

### Input

First line contains two integers V and E denoting number of houses and number of pipelines respectively. Second line contains n integer denoting cost to dig well at ith house. Each of next E lines contain 3 numbers ui and vi and c denoting a pipeline between u and v with cost c to build.

### Output

Return the minimum total cost to supply water to all the construction sites.

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}3 2 1 2 2 1 2 1 2 3 1 ```

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}3 ```

Discussions

Show Discussion

Related Resources