fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. int m, n;
  5. bool taken[10001];
  6. vector<pair<int,int>> adj[10001];
  7.  
  8. void nhap() {
  9.     cin >> n >> m ;
  10.     for(int i = 0 ; i < m ; i++) {
  11.         int x, y, w;
  12.         cin >> x >> y >> w;
  13.         adj[x].push_back({y, w});
  14.         adj[y].push_back({x, w});
  15.     }
  16. }
  17.  
  18. void Prim(int s) {
  19.     taken[s] = true;
  20.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
  21.     for(auto it : adj[s]) {
  22.         int t = it.first;
  23.         if(!taken[t]) {
  24.             Q.push({it.second, t});
  25.         }
  26.     }
  27.     ll d = 0 , dem = 0 ;
  28.     while(!Q.empty()) {
  29.         // lay ra canh ngan nhat
  30.         pair<int,int> e = Q.top();
  31.         Q.pop();
  32.         int u = e.second;
  33.         int w = e.first;
  34.         if(!taken[u]) {
  35.             ++dem;
  36.             d += w;
  37.             taken[u] = true;
  38.             for(auto it : adj[u]) {
  39.                 if(!taken[it.first]) {
  40.                     Q.push({it.second, it.first});
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     if(dem == n - 1) {
  46.         cout << d << endl;
  47.     }
  48.     else {
  49.         cout << "IMPOSSIBLE\n";
  50.     }
  51. }
  52.  
  53. int main() {
  54.     nhap();
  55.     Prim(1);
  56. }
  57.  
Success #stdin #stdout 0s 5296KB
comments (?)
stdin
copy 
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7

5 4 4
stdout
copy 
14
https://ideone.com/1QvJg8
Prim
language:
C++ (gcc 8.3)
created:
14 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!