Advertisement
Guest User

Untitled

a guest
Mar 30th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. using namespace std;
  5.  
  6. struct point {
  7. int x;
  8. int y;
  9. };
  10.  
  11. int distance (point &a, point &b) {
  12. return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  13. }
  14.  
  15. int main() {
  16. freopen("spantree.in", "r", stdin);
  17. freopen("spantree.out", "w", stdout);
  18.  
  19. int n;
  20. cin >> n; //n <=5000
  21. vector <point> p(n);
  22. vector <bool> visited(n);
  23. vector<int> Min(n, INT32_MAX);
  24. int dist[n][n];
  25.  
  26. for (int i = 0; i < n; ++i) {
  27. visited[i] = false;
  28. cin >> p[i].x >> p[i].y; //-10 000 <= x, y <= 10 000
  29. }
  30.  
  31. for (int i = 0; i < n; ++i)
  32. for (int j = 0; j < n; ++j) {
  33. dist[i][j] = distance(p[i], p[j]);
  34. }
  35.  
  36. Min[0] = 0;
  37. for (int i = 0; i < n; ++i) {
  38. int v = -1;
  39. for (int j = 0; j < n; ++j)
  40. if (!visited[j] && (v == -1 || Min[j] < Min[v]))
  41. v = j;
  42.  
  43. visited[v] = true;
  44.  
  45. for (int to = 0; to < n; ++to)
  46. if (!visited[to] && dist[v][to] < Min[to] && v != to) {
  47. Min[to] = dist[v][to];
  48. }
  49. }
  50.  
  51. double ans = 0.0;
  52. for (int i : Min) {
  53. ans = ans + sqrt(i);
  54. }
  55.  
  56. cout.precision(10);
  57. cout << ans;
  58. return 0;
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement