{"id":"ce134270-991e-4144-9ac1-4b8833364f74","name":"Minimum Cost To Connect All Cities","description":"There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads. ","inputFormat":"First line contains number of cities.\r\nSecond line contains number of edges roads.\r\nEach of next E lines contain 3 number u and v and c denoting a road between u and v with cost c to repair.","outputFormat":"print the minimum cost.","constraints":"1&lt;= n &lt;= 1000\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Edge{\n public:\n int v;\n int wt;\n Edge(int v,int wt)\n {\n this->v=v;\n this->wt=wt;\n }\n};\n\n\nint main()\n{\n int vtces;\n cin>>vtces;\n vector<vector<Edge>> graph(vtces);\n int edges;cin>>edges;\n for(int i=0;i<edges;++i)\n {\n int v1;cin>>v1;\n int v2;cin>>v2;\n int wt;cin>>wt;\n graph[v1].push_back(Edge(v2,wt));\n graph[v2].push_back(Edge(v1,wt));\n }\n \n\n \n return 0;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n static class Edge implements Comparable<Edge> {\n int v;\n int wt;\n\n Edge(int nbr, int wt) {\n this.v = nbr;\n this.wt = wt;\n }\n\n @Override\n public int compareTo(Edge o) {\n return this.wt - o.wt;\n }\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int vtces = Integer.parseInt(br.readLine());\n ArrayList<ArrayList<Edge>> graph = new ArrayList<>();\n for (int i = 0; i < vtces; i++) {\n graph.add(new ArrayList<>());\n }\n\n int edges = Integer.parseInt(br.readLine());\n for (int i = 0; i < edges; i++) {\n String[] parts = br.readLine().split(\" \");\n int v1 = Integer.parseInt(parts[0]);\n int v2 = Integer.parseInt(parts[1]);\n int wt = Integer.parseInt(parts[2]);\n graph.get(v1).add(new Edge(v2, wt));\n graph.get(v2).add(new Edge(v1, wt));\n }\n \n \n\n }\n\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8","sampleOutput":"38\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":"23ab7810-ea26-41e2-8bfa-04d63b461b85","name":"Minimum Cost To Connect All Cities","slug":"minimum-cost-to-connect-all-cities","type":1}],"next":{"id":"62bc6c62-a2d8-4d84-8faf-b48e40b2ec9b","name":"Minimum cost to connect all cities Medium","type":0,"slug":"minimum-cost-to-connect-all-cities-medium"},"prev":{"id":"d632c0b7-6f5e-4759-add6-a67cb4ede19a","name":"KRUSKALS ALGORITHM","type":3,"slug":"kruskals-algorithm"}}}

Minimum Cost To Connect All Cities

There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads.

{"id":"ce134270-991e-4144-9ac1-4b8833364f74","name":"Minimum Cost To Connect All Cities","description":"There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads. ","inputFormat":"First line contains number of cities.\r\nSecond line contains number of edges roads.\r\nEach of next E lines contain 3 number u and v and c denoting a road between u and v with cost c to repair.","outputFormat":"print the minimum cost.","constraints":"1&lt;= n &lt;= 1000\r\n1&lt;= e &lt;= n*(n-1)/2","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nclass Edge{\n public:\n int v;\n int wt;\n Edge(int v,int wt)\n {\n this->v=v;\n this->wt=wt;\n }\n};\n\n\nint main()\n{\n int vtces;\n cin>>vtces;\n vector<vector<Edge>> graph(vtces);\n int edges;cin>>edges;\n for(int i=0;i<edges;++i)\n {\n int v1;cin>>v1;\n int v2;cin>>v2;\n int wt;cin>>wt;\n graph[v1].push_back(Edge(v2,wt));\n graph[v2].push_back(Edge(v1,wt));\n }\n \n\n \n return 0;\n}"},"java":{"code":"import java.io.*;\nimport java.util.*;\n\npublic class Main {\n static class Edge implements Comparable<Edge> {\n int v;\n int wt;\n\n Edge(int nbr, int wt) {\n this.v = nbr;\n this.wt = wt;\n }\n\n @Override\n public int compareTo(Edge o) {\n return this.wt - o.wt;\n }\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n\n int vtces = Integer.parseInt(br.readLine());\n ArrayList<ArrayList<Edge>> graph = new ArrayList<>();\n for (int i = 0; i < vtces; i++) {\n graph.add(new ArrayList<>());\n }\n\n int edges = Integer.parseInt(br.readLine());\n for (int i = 0; i < edges; i++) {\n String[] parts = br.readLine().split(\" \");\n int v1 = Integer.parseInt(parts[0]);\n int v2 = Integer.parseInt(parts[1]);\n int wt = Integer.parseInt(parts[2]);\n graph.get(v1).add(new Edge(v2, wt));\n graph.get(v2).add(new Edge(v1, wt));\n }\n \n \n\n }\n\n}"},"python":{"code":""}},"points":10,"difficulty":"easy","sampleInput":"7\r\n8\r\n0 1 10\r\n1 2 10\r\n2 3 10\r\n0 3 40\r\n3 4 2\r\n4 5 3\r\n5 6 3\r\n4 6 8","sampleOutput":"38\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":"23ab7810-ea26-41e2-8bfa-04d63b461b85","name":"Minimum Cost To Connect All Cities","slug":"minimum-cost-to-connect-all-cities","type":1}],"next":{"id":"62bc6c62-a2d8-4d84-8faf-b48e40b2ec9b","name":"Minimum cost to connect all cities Medium","type":0,"slug":"minimum-cost-to-connect-all-cities-medium"},"prev":{"id":"d632c0b7-6f5e-4759-add6-a67cb4ede19a","name":"KRUSKALS ALGORITHM","type":3,"slug":"kruskals-algorithm"}}}
plane

Editor

Loading...

Minimum Cost To Connect All Cities

easy

There are n cities and there are roads in between some of the cities. Somehow all the roads are damaged simultaneously. We have to repair the roads to connect the cities again. There is a fixed cost to repair a particular road. Find out the minimum cost to connect all the cities by repairing roads.

Constraints

1<= n <= 1000 1<= e <= n*(n-1)/2

Format

Input

First line contains number of cities. Second line contains number of edges roads. Each of next E lines contain 3 number u and v and c denoting a road between u and v with cost c to repair.

Output

print the minimum cost.

Example

Sample Input

7 8 0 1 10 1 2 10 2 3 10 0 3 40 3 4 2 4 5 3 5 6 3 4 6 8

Sample Output

38

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode