Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
88
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int INF = 1e9;
  7.  
  8. int main()
  9. {
  10. freopen("unionday.in", "r", stdin);
  11. freopen("unionday.out", "w", stdout);
  12. int n; cin >> n;
  13. double g[n][n];
  14.  
  15. //g.resize(n);
  16.  
  17. //for (int i = 0;i < n; i++) g[i].resize(n);
  18.  
  19. vector <pair <int, int> > point(n);
  20.  
  21. for (int i = 0; i < n; i++){
  22. int x,y; scanf("%d %d", &x, &y);
  23. point[i] = make_pair(x, y);
  24. }
  25.  
  26. for (int i = 0; i < n; i++){
  27. for (int j = 0; j < n; j++){
  28. double cost = ((point[i].first - point[j].first)*(point[i].first - point[j].first) + (point[i].second - point[j].second) * (point[i].second - point[j].second));
  29. g[i][j] = cost;
  30. g[j][i] = cost;
  31. }
  32. }
  33.  
  34. vector <bool> used(n);
  35. vector <int> min_edge(n, INF), end_edge(n, -1);
  36. min_edge[0] = 0;
  37.  
  38. double ans = 0;
  39.  
  40. for (int i = 0; i < n; i++){
  41. int v = -1;
  42. for (int j = 0; j < n; j++)
  43. if (!used[j] && (v == -1 || min_edge[j] < min_edge[v]))
  44. v = j;
  45.  
  46.  
  47. used[v] = 1;
  48.  
  49. if (end_edge[v] != -1) ans += sqrtl(g[v][end_edge[v]]);
  50.  
  51. for (int to = 0; to < n; to++)
  52. if (g[v][to] < min_edge[to]){
  53. min_edge[to] = g[v][to];
  54. end_edge[to] = v;
  55. }
  56. }
  57.  
  58. printf("%f", ans);
  59.  
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement