SHARE
TWEET

3C

a guest Mar 24th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5.  
  6.  
  7. int main() {
  8.     std::fstream filein("spantree2.in");
  9.     unsigned short int n;
  10.     filein >> n;
  11.     std::vector < std::pair<unsigned short int ,int> > g[n];
  12.     std::vector<int> min_e (n, 100002);
  13.     bool used[n];
  14.     for (int i = 0; i < n; ++i) {
  15.         used[i] = false;
  16.     }
  17.     long long int result = 0;
  18.     int m, weight;
  19.     filein >> m;
  20.     unsigned short int vert1, vert2;
  21.     for (int i = 0; i < m; ++i) {
  22.         filein >> vert1 >> vert2 >> weight;
  23.         g[vert1 - 1].emplace_back(std::make_pair (vert2 - 1, weight));
  24.         g[vert2 - 1].emplace_back(std::make_pair (vert1 - 1, weight));
  25.     }
  26.  
  27.     std::set < std::pair<int,unsigned short int> > q;
  28.     q.insert (std::make_pair (0, 0));
  29.     for (int i = 0; i < n; ++i) {
  30.         result += q.begin()->first;
  31.         unsigned short int v = q.begin()->second;
  32.         used[v] = true;
  33.  
  34.         q.erase (q.begin());
  35.         for (size_t j=0; j<g[v].size(); ++j) {
  36.             int to = g[v][j].first,
  37.                     cost = g[v][j].second;
  38.             if (cost < min_e[to] && !used[to]) {
  39.                 q.erase (std::make_pair (min_e[to], to));
  40.                 min_e[to] = cost;
  41.                 q.insert (std::make_pair (min_e[to], to));
  42.             }
  43.         }
  44.     }
  45.  
  46.     std::ofstream fileout("spantree2.out");
  47.     fileout << result;
  48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top