Advertisement
Josif_tepe

Untitled

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