Advertisement
Josif_tepe

Untitled

Dec 26th, 2022
739
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <cstring>
  5. #include <queue>
  6. #include <algorithm>
  7. using namespace std;
  8. const int maxn = 1e5 + 10;
  9. vector<pair<int, int> > graph[maxn];
  10. struct node {
  11.     int idx, cost;
  12.     node () {}
  13.     node(int _idx, int _cost) {
  14.         idx = _idx;
  15.         cost = _cost;
  16.     }
  17.     bool operator < (const node &t) const {
  18.         return cost > t.cost;
  19.     }
  20. };
  21. int main() {
  22.  
  23.     int n, m;
  24.     cin >> n >> m;
  25.     for(int i = 0; i < m; i++) {
  26.         int a, b, c;
  27.         cin >> a >> b >> c;
  28.         a--;
  29.         b--;
  30.         graph[a].push_back(make_pair(b, c));
  31.         graph[b].push_back(make_pair(a, c));
  32.     }
  33.    
  34.     vector<bool> visited(n + 1, false);
  35.     vector<int> dist(n + 1, 2e9);
  36.     dist[0] = 0;
  37.     priority_queue<node> pq;
  38.     pq.push(node(0, 0));
  39.     int MST = 0;
  40.    
  41.     while(!pq.empty()) {
  42.         node c = pq.top();
  43.         pq.pop();
  44.         if(visited[c.idx]) continue;
  45.         visited[c.idx] = true;
  46.         MST += c.cost;
  47.        
  48.         for(int i = 0; i < (int) graph[c.idx].size(); i++) {
  49.             int neighbour = graph[c.idx][i].first;
  50.             int weight = graph[c.idx][i].second;
  51.             if(!visited[neighbour] and weight < dist[neighbour]) {
  52.                 dist[neighbour] = weight;
  53.                 pq.push(node(neighbour, weight));
  54.             }
  55.         }
  56.        
  57.     }
  58.     cout << MST << endl;
  59.    
  60.    
  61.     return 0;
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement