Advertisement
Guest User

3C

a guest
Mar 24th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement