ccbeginner

TIOJ 2164

Oct 24th, 2020
372
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <time.h>
  3. using namespace std;
  4. #define SZ(x) (int)(x.size())
  5. #define int long long
  6.  
  7. int x[5001], y[5001], z[5001];
  8. int dist[5001][5001];
  9. int key[5001];
  10. int pre[5001];
  11. bool choose[5001];
  12.  
  13. int32_t main(){
  14.     int n;
  15.     scanf("%lld", &n);
  16.     if(n > 5000)return 0;
  17.     for(int i = 1; i <= n; ++i){
  18.         scanf("%lld%lld%lld", x+i, y+i, z+i);
  19.         key[i] = 1e18;
  20.     }
  21.     for(int i = 1; i <= n; ++i){
  22.         for(int j = 1; j <= n; ++j){
  23.             dist[i][j] += (x[i]-x[j])*(x[i]-x[j]);
  24.             dist[i][j] += (y[i]-y[j])*(y[i]-y[j]);
  25.             dist[i][j] += (z[i]-z[j])*(z[i]-z[j]);
  26.         }
  27.     }
  28.     int ans = 0;
  29.     key[1] = 0;
  30.     for(int i = 1; i <= n; ++i){
  31.         int small = -1;
  32.         for(int j = 1; j <= n; ++j){
  33.             if(!choose[j] && (small == -1 || key[j] < key[small])){
  34.                 small = j;
  35.             }
  36.         }
  37.         choose[small] = 1;
  38.         ans += dist[small][pre[small]];
  39.         //cout << small << ' ' << pre[small] << '\n';
  40.         for(int j = 1; j <= n; ++j){
  41.             if(key[j] > dist[small][j]){
  42.                 key[j] = dist[small][j];
  43.                 pre[j] = small;
  44.             }
  45.         }
  46.     }
  47.     cout << ans << '\n';
  48.     return 0;
  49. }
RAW Paste Data