{"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"}}}
plane

Editor


Loading...

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

3 2 1 2 2 1 2 1 2 3 1

Sample Output

3

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode