fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>	
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vl;
  8. typedef pair<int, int>pi;
  9. typedef pair<ll, ll>pl;
  10. typedef vector<pi>vpi;
  11. typedef vector<pl>vpl;
  12. typedef vector<vi> vvi;
  13. typedef vector<vl> vvl;
  14. typedef vector<string> vs;
  15. typedef vector<bool> vb;
  16. const long double PI = acos(-1);
  17. const ll oo = 1e18 + 7;
  18. const int MOD = 1e9 + 7;
  19. const int N = 2e5 + 7;
  20. #define all(v) (v).begin(),(v).end()
  21. #define rall(v) (v).rbegin(),(v).rend()
  22. #define read(v) for (auto& it : v) scanf("%d", &it);
  23. #define readl(v) for (auto& it : v) scanf("%lld", &it);
  24. #define print(v) for (auto it : v) printf("%d ", it); puts("");
  25. #define printl(v) for (auto it : v) printf("%lld ", it); puts("");
  26. int n,m,p[N],cnt=0;
  27. int find(int u){
  28.     if(u==p[u])
  29.         return u;
  30.     return p[u]=find(p[u]);
  31. }
  32. void unite(int u,int v){
  33.     u=find(u),v=find(v);
  34.     if(u==v)
  35.         return;
  36.     p[v]=u;
  37.     cnt--;
  38. }
  39. void solve() {
  40.     scanf("%d %d",&n,&m);
  41.     for(int i=0;i<=n;i++)
  42.         p[i]=i;
  43.     cnt=n;
  44. 	vector<pair<ll, pl>>edges;
  45. 	for (int i = 0, a, b, c; i < m; i++) {
  46. 		scanf("%d %d %d", &a, &b, &c);
  47. 		edges.push_back({(ll) c,{a,b} });
  48. 	}
  49. 	sort(all(edges));
  50.     ll ans=0;
  51.     for(auto&it:edges){
  52.         ll u=it.second.first,v=it.second.second;
  53.         ll w=it.first;
  54.         u=find(u),v=find(v);
  55.         if(u!=v){
  56.             ans+=w;
  57.             unite(u,v);
  58.         }
  59.     }
  60.     if(cnt>1){
  61.         cout<<"IMPOSSIBLE"<<endl;
  62.         return;
  63.     }
  64.     printf("%lld\n",ans);
  65. }
  66. int t = 1;
  67. int main() {
  68. 	//scanf("%d", &t);
  69. 	while (t--) solve();
  70. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/eIN1Ll
language:
C++14 (gcc 8.3)
created:
1 day 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!