SHARE
TWEET

Untitled

a guest Mar 24th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top