Advertisement
kolbka_

Untitled

Mar 17th, 2022
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <unordered_map>
  5. #include <string>
  6. #include <vector>
  7. #include <iostream>
  8. #include <set>
  9. #include <queue>
  10. #include "optimization.h"
  11. #include <math.h>
  12. #include <unordered_map>
  13. #include <iomanip>
  14.  
  15. using namespace std;
  16. struct town {
  17.     int x;
  18.     int y;
  19. };
  20.  
  21.  
  22.  
  23.  
  24. int main() {
  25.     vector<tuple<double, int, int>> edges;
  26.     cout.tie(0);
  27.     cin.tie(0);
  28.     ios_base::sync_with_stdio(0);
  29.     int n = readInt();
  30. //    cin >> n;
  31.     vector<town> towns(n);
  32.  
  33.     for (int i = 0; i < n; i++) {
  34. //        cin >> towns[i].x >> towns[i].y;
  35.         towns[i].x = readInt(); towns[i].y = readInt();
  36.  
  37.     }
  38.  
  39.     double answer = 0;
  40.     vector<int> dist(n, INT32_MAX);
  41.     dist[0] = 0;
  42.     vector<bool> mark(n, false);
  43.     for (int i = 0; i < n; i++){
  44.         int cur_v = -1;
  45.         for (int j = 0; j < n; j++){
  46.             if (!mark[j] && (cur_v == -1 || dist[j] < dist[cur_v])) cur_v = j;
  47.         }
  48.         answer += sqrt(dist[cur_v]);
  49.         mark[cur_v] = true;
  50.         for (int k =0; k < n; k++){
  51.             if (!mark[k]){
  52.                 dist[k] = min(dist[k], (towns[k].x - towns[cur_v].x) * (towns[k].x - towns[cur_v].x) + (towns[k].y - towns[cur_v].y) * (towns[k].y - towns[cur_v].y));
  53.             }
  54.         }
  55.     }
  56. //    cout << std::setprecision(10) << answer;
  57.     writeDouble(answer, 10);
  58. }
  59.  
  60.  
  61.  
  62.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement