Advertisement
tepyotin2

Prim Algorithm

Jun 1st, 2025
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Con{
  6.     int node, weight;
  7.     bool operator>(const Con & a) const{
  8.         return weight>a.weight;
  9.         //need to sort the same way as usual for priority queue because greater<int> already sorts the value how we want
  10.     }
  11. };
  12.  
  13. int n, m;
  14. vector<vector<Con>> con;
  15. int ans;
  16. vector<bool> visited;
  17. vector<int> dist;
  18. priority_queue<Con, vector<Con>, greater<Con>> pq;
  19.  
  20. int main(){
  21.     //freopen("prims.in", "r", stdin);
  22.    
  23.     cin >> n >> m;
  24.     con.resize(n+1);
  25.     visited.resize(n+1);
  26.     dist.resize(n+1, INT_MAX);
  27.     for(int i=0; i<m; i++){
  28.         int a, b, c;
  29.         cin >> a >> b >> c;
  30.         con[a].push_back({b, c});
  31.         con[b].push_back({a, c});
  32.     }
  33.     pq.push({1, 0});
  34.     dist[1] = 0;
  35.     while(!pq.empty()){
  36.         Con cur = pq.top();
  37.         pq.pop();
  38.         if(visited[cur.node]) continue;
  39.         visited[cur.node] = true;
  40.         ans+=cur.weight;
  41.         for(Con next: con[cur.node]){
  42.             if(!visited[next.node] && cur.weight<dist[next.node]){
  43.                 dist[next.node] = next.weight;
  44.                 //do not need to equal to value of weights combined just the weight of the next one
  45.                 pq.push({next.node, dist[next.node]});
  46.             }
  47.         }
  48.     }
  49.     cout << ans << '\n';
  50.    
  51.     return 0;
  52. }
  53.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement