Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. using namespace std;
  6. #define mp make_pair
  7.  
  8. vector<pair<int, int>> point;
  9.  
  10. double dist(int i1, int i2) {
  11. auto p1 = point[i1];
  12. auto p2 = point[i2];
  13. return sqrt((p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second));
  14. }
  15.  
  16. vector<double> dst;
  17.  
  18. int main() {
  19. int n;
  20. cin >> n;
  21. dst.resize(n, 1e9);
  22. for (int i = 0; i < n; ++i) {
  23. int x, y;
  24. cin >> x >> y;
  25. point.emplace_back(x, y);
  26. }
  27.  
  28. vector<bool> used(n,false);
  29. dst[0] = 0;
  30. for (;;) {
  31. int v = -1;
  32. for (int i = 0; i < n; ++i) {
  33. if (!used[i] && dst[i] < 1e9 && (v==-1 || dst[v] > dst[i])) {
  34. v = i;
  35. }
  36. }
  37. if (v==-1) break;
  38. used[v] = true;
  39. for (int i = 0; i < n; ++i) {
  40. if (!used[i]) {
  41. dst[i] = min(dst[i], dist(v,i));
  42. }
  43. }
  44. }
  45.  
  46. double res =0;
  47. for(int i=0;i<n;++i) {
  48. res += dst[i];
  49. }
  50. printf("%.10f",res);
  51. return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement