fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const ll MAXN = 200005;
  5. #define fi first
  6. #define se second
  7. #define pr pair<int,pair<int,int>>
  8.  
  9.  
  10. vector <vector<pair<int,int>>> A(MAXN);
  11. vector <pr> vet;
  12. priority_queue<pr,vector<pr>,greater<pr>> Q;
  13.  
  14. void prim(int u,int n){
  15. 	vector <bool> ktra(n+1,true);
  16.     ll ans=0;
  17.     for(auto [c,t]:A[u]) Q.push({t,{u,c}});
  18.     ktra[u]=false;
  19.     while(!Q.empty()){
  20.         auto canh=Q.top(); Q.pop();
  21.         ll trongso=canh.fi, dau=canh.se.fi, cuoi=canh.se.se;
  22.         if(!ktra[cuoi]) continue;
  23.         ans+=trongso;   
  24.         //cout << "(" <<dau <<","<<cuoi<<")" << " = " << trongso << "\n";
  25.         //vet.push_back({trongso,{dau,cuoi}});
  26.         ktra[cuoi]=false;
  27.         for(auto it:A[cuoi]){
  28.             if(ktra[it.fi]){
  29.                 Q.push({it.se,{cuoi,it.fi}});
  30.             }
  31.         }
  32.  
  33.     }
  34.     cout << ans <<"\n";
  35. }
  36.  
  37. int main(){
  38.     //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  39.  
  40.     ll n,m; cin >> n >> m;
  41.     for(ll i=1 ; i<=m ; i++){
  42.         ll z,x,y; cin >> x >> y >> z;
  43.         A[x].push_back({y,z});
  44.         A[y].push_back({x,z});
  45.     }
  46.     prim(1,n);
  47.     /*
  48.     for(ll i=1 ; i<=n ; i++){
  49.         cout << i << " : ";
  50.         for(auto [x,y]:A[i]) cout << x << "-" << y << " ";
  51.         cout << endl;
  52.     }
  53.     */
  54. }
  55.  
Time limit exceeded #stdin #stdout 5s 1941000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pRYken
language:
C++ (gcc 8.3)
created:
149 days 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!