kananasgarli90

Minimal çərçivə

Sep 28th, 2020
848
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 1000000
  4. int color[20001];
  5. vector<pair<int, int> >adj[20001];
  6. set<int>s;
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.     int n, m, u, v, w, a, b, mst = 0, x, min_weight;
  12.     cin>>n>>m;
  13.     while(m--){
  14.         cin>>u>>v>>w;
  15.         adj[u].push_back(make_pair(v, w));
  16.         adj[v].push_back(make_pair(u, w));
  17.     }
  18.     color[1] = 1;
  19.     s.insert(1);
  20.     while(s.size() != n){
  21.         min_weight = INF;
  22.         for(auto i = s.begin(); i != s.end(); i++){
  23.             a = *i;
  24.             for(int j = 0; j < adj[a].size(); j++){
  25.                 x = adj[a][j].first;
  26.                 if(color[x] == 0 && adj[a][j].second < min_weight){
  27.                     min_weight = adj[a][j].second;
  28.                     b = x;
  29.                 }
  30.             }
  31.         }
  32.         color[b] = 1;
  33.         s.insert(b);
  34.         mst += min_weight;
  35.     }
  36.  
  37.     cout<<mst<<endl;
  38. }
  39.  
RAW Paste Data