fork(1) download
copy 
  1. /**
  2. 	Template by proptit_4t41
  3. 	Applied for C++11/C++14
  4. 	Add -std=c++14 to your IDE.
  5. **/
  6.  
  7. /**
  8. 	// code written by a random fan of momocashew
  9. 	// world.execute(me);
  10. **/
  11.  
  12. /**
  13. 	To make it compatible to C++98,
  14. 	remove all tuple typedefs, unordered
  15. 	sets/maps/multisets/multimaps, and add
  16. 	a space between two '<'/'>'s when declaring
  17. 	multi-dimensional vectors (to avoid ambiguity).
  18. **/
  19.  
  20. #include <bits/stdc++.h>
  21. using namespace std;
  22.  
  23. /** -----BASIC MACROES----- **/
  24. #define endl '\n'
  25. #define i64 long long
  26. #define u64 unsigned long long
  27. #define ld long double
  28. #define pub push_back
  29. #define puf push_front
  30. #define pob pop_back
  31. #define pof pop_front
  32. #define mmap multimap
  33. #define mset multiset
  34. #define umap unordered_map
  35. #define uset unordered_set
  36. #define ummap unordered_multimap
  37. #define umset unordered_multiset
  38. #define mp make_pair
  39. #define mt make_tuple
  40. #define fi first
  41. #define se second
  42. #define REcheck cout << "RE here?\n"
  43. #define tracker1(i) cout << "working at " << i << endl;
  44. #define tracker2(i,j) cout << "working at " << i << "-" << j << endl;
  45. #define tracker3(i,j,k) cout << "working at " << i << "-" << j << "-" << k << endl;
  46. const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230;
  47. const long long MOD = 1000000007LL;
  48. const long long INF = 1e9;
  49. const long long LINF = 1e18;
  50. const long double EPS = 1e-9;
  51. const long double GOLD = ((1+sqrt(5))/2);
  52. typedef pair<i64, i64> pii;
  53. typedef pair<i64, pii> pip;
  54. typedef pair<pii, i64> ppi;
  55. typedef tuple<i64, i64> tii;
  56. typedef tuple<i64, i64, i64> tiii;
  57.  
  58. /** -----BIT CONTROLS----- **/
  59. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  60. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  61. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  62. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  63.  
  64. /** -----IDEAS/ALGORITHMS-----
  65.  
  66.     -------------------------- **/
  67.  
  68. /// MAIN SOLUTION STARTS HERE
  69.  
  70. /** -----CUSTOM TYPEDEFS----- **/
  71.  
  72.  
  73. /** -----GLOBAL VARIABLES----- **/
  74. //int T, cas = 0; // for multi-testcase problems
  75. i64 n, m, ans = 0; vector<vector<pii>> adj;
  76. vector<i64> chosen;
  77. priority_queue<pii> Q;
  78.  
  79. /** -----EXTENSIVE FUNCTIONS----- **/
  80.  
  81.  
  82. /** -----COMPULSORY FUNCTIONS----- **/
  83. void VarInput() {
  84. 	//cin >> T; // for multi-testcase problems
  85. 	cin >> n >> m; adj.resize(n+1, vector<pii>(0));
  86. 	chosen.resize(n+1, false);
  87. 	Q.push(mp(0, 1));
  88. 	while (m--) {
  89. 		i64 a, b, c; cin >> a >> b >> c;
  90. 		adj[a].pub(mp(b,c)); adj[b].pub(mp(a,c));
  91. 	}
  92. }
  93.  
  94. void ProSolve() {
  95. 	//cout << "Case " << ++cas << ": " << ans << endl; // for multi-testcase problems
  96. 	while (!Q.empty()) {
  97. 		i64 z = Q.top().se;
  98. 		i64 tmp = Q.top().fi; Q.pop();
  99. 		if (chosen[z]) continue; chosen[z] = true;
  100. 		ans -= tmp;
  101. 		for (i64 i=0; i<adj[z].size(); i++) {
  102. 			pii zz = adj[z][i];
  103. 			if (chosen[zz.fi]) continue;
  104. 			Q.push(mp(-zz.se, zz.fi));
  105. 		}
  106. 	}
  107. 	cout << ans;
  108. }
  109.  
  110. /** -----MAIN FUNCTION----- **/
  111. int main() {
  112. 	//freopen("FILE.INP", "r", stdin);
  113. 	//freopen("FILE.OUT", "w", stdout);
  114. 	ios_base::sync_with_stdio(0); cin.tie(NULL);
  115. 	VarInput();
  116. 	//while(T--) ProSolve(); // for multi-testcase problems
  117. 	ProSolve(); // for regular problems
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 4200KB
comments (?)
stdin
copy 
6 9
1 2 1
1 3 1
2 4 1
2 3 2
2 5 1
3 5 1
3 6 1
4 5 2
5 6 2
stdout
copy 
5
https://ideone.com/O1nI1m
Minimum Spanning Tree - Prim's Algorithm
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!