Advertisement
Stepavly

Untitled

Jul 16th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.18 KB | None | 0 0
  1. #include <math.h>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. struct pt
  9. {
  10. ll x, y;
  11. };
  12.  
  13. double dist(const pt& a, const pt& b)
  14. {
  15. return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  16. }
  17.  
  18. double g[5000][5000];
  19. int chosenV[5000];
  20. double minD[5000];
  21. char used[5000];
  22.  
  23. int main()
  24. {
  25. ios_base::sync_with_stdio(0);
  26. cin.tie(0);
  27. cout.setf(cout.fixed);
  28. cout.precision(12);
  29.  
  30. int n;
  31. cin >> n;
  32.  
  33. vector<pt> pts(n);
  34.  
  35. for (int i = 0; i < n; i++)
  36. {
  37. cin >> pts[i].x >> pts[i].y;
  38. }
  39.  
  40. for (int i = 0; i < n; i++)
  41. {
  42. for (int j = i + 1; j < n; j++)
  43. {
  44. g[i][j] = g[j][i] = dist(pts[i], pts[j]);
  45. }
  46. }
  47.  
  48. fill(chosenV, chosenV + n, -1);
  49. fill(minD, minD + n, INF);
  50.  
  51. minD[0] = 0;
  52. double res = 0;
  53.  
  54. for (int i = 0; i < n; i++)
  55. {
  56. int v = -1;
  57.  
  58. for (int j = 0; j < n; j++)
  59. {
  60. if (!used[j] && (v == -1 || minD[v] > minD[j]))
  61. {
  62. v = j;
  63. }
  64. }
  65.  
  66. used[v] = 1;
  67.  
  68. if (chosenV[v] != -1)
  69. res += g[v][chosenV[v]];
  70.  
  71. for (int j = 0; j < n; j++)
  72. {
  73. if (minD[j] > g[v][j])
  74. {
  75. minD[j] = g[v][j];
  76. chosenV[j] = v;
  77. }
  78. }
  79. }
  80.  
  81. cout << res;
  82.  
  83. return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement