kananasgarli90

Prim - priority queue

Oct 31st, 2020
713
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define INF 2000000000
  4. vector<pair<int, int> > g[20001];
  5. priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >pq;
  6. int n, m, a, b, w, MST, key[20001], color[20001];
  7. void Prim(){
  8.     for(int i = 2; i <= n; i++){
  9.         key[i] = INF;
  10.     }
  11.     pq.push(make_pair(0, 1));
  12.     while(pq.size() != 0){
  13.         int min_vertex = pq.top().second;
  14.         pq.pop();
  15.         if(color[min_vertex] == 1){
  16.             continue;
  17.         }
  18.         for(int i = 0; i < g[min_vertex].size(); i++){
  19.             int u = g[min_vertex][i].first;
  20.             if(color[u] == 0 && key[u] > g[min_vertex][i].second){
  21.                 key[u] = g[min_vertex][i].second;
  22.                 pq.push(make_pair(key[u], u));
  23.             }
  24.         }
  25.         color[min_vertex] = 1;
  26.         MST += key[min_vertex];
  27.     }
  28. }
  29. int main()
  30. {
  31.     cin>>n>>m;
  32.     while(m--){
  33.         cin>>a>>b>>w;
  34.         g[a].push_back(make_pair(b, w));
  35.         g[b].push_back(make_pair(a, w));
  36.     }
  37.     Prim();
  38.     cout<<MST<<endl;
  39. }
RAW Paste Data