fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int spanningTree(int V, vector<vector<int>> edges){
  6. 	priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
  7. 	vector<bool> visited(V,false);
  8. 	vector<vector<pair<int,int>>> adj_list(V);
  9. 	for(int i=0;i<edges.size();i++){
  10. 		int start = edges[i][0];
  11. 		int end = edges[i][1];
  12. 		int weight = edges[i][2];
  13. 		adj_list[start].push_back({end,weight});
  14. 		adj_list[end].push_back({start,weight});
  15. 	}
  16. 	int sum = 0;
  17. 	visited[0] = true;
  18. 	for(int i=0;i<adj_list[0].size();i++){
  19. 		int dest = adj_list[0][i].first;
  20. 		int weight = adj_list[0][i].second;
  21. 		pq.push({weight,make_pair(0,dest)});
  22. 	}
  23. 	while(!pq.empty()){
  24. 		auto temp = pq.top();
  25. 		pq.pop();
  26. 		int start = temp.second.first;
  27. 		int end = temp.second.second;
  28. 		int weight = temp.first;
  29. 		if((visited[start] and !visited[end])){
  30. 			visited[end] = true;
  31. 			for(int i=0;i<adj_list[end].size();i++){
  32. 				int dest = adj_list[end][i].first;
  33. 				int weight = adj_list[end][i].second;
  34. 				pq.push({weight,make_pair(end,dest)});
  35. 			}
  36. 			sum+=weight;
  37. 		}
  38. 		else if(!visited[start] and visited[end]){
  39. 			visited[start] = true;
  40. 			for(int i=0;i<adj_list[start].size();i++){
  41. 				int dest = adj_list[start][i].first;
  42. 				int weight = adj_list[start][i].second;
  43. 				pq.push({weight,make_pair(start,dest)});
  44. 			}
  45. 			sum+=weight;
  46. 		}
  47. 	}
  48. 	return sum;
  49. }
  50.  
  51. int main() {
  52. 	int V = 5;
  53. 	vector<vector<int>> edges = {{0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}};
  54.  
  55. 	int sum = spanningTree(V, edges);
  56. 	cout << "The sum of all the edge weights: " << sum << endl;
  57.  
  58. 	return 0;
  59. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The sum of all the edge weights: 5
https://ideone.com/fmZKPY
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!