Fshl0

Prim

Jul 11th, 2020
139
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll Prim (int x) {
  2.     //PII = pair<ll, ll>
  3.     priority_queue <PII, vector<PII>, greater<PII> > Q;
  4.     ll total = 0;
  5.     PII p;
  6.     Q.push({0, x});
  7.     while (!Q.empty()) {
  8.         p = Q.top();
  9.         Q.pop();
  10.         x = p.S;
  11.         if (vis[x] == true) continue;
  12.         total += p.first;
  13.         vis[x] = true;
  14.         for (ll i = 0; i < adj[x].size(); i++) {
  15.             ll y = adj[x][i].S;
  16.             if (vis[y] == false)
  17.                 Q.push(adj[x][i]);
  18.         }
  19.     }
  20.     return total;
  21. }
RAW Paste Data