C++(g++ 7.5.0) 解法, 执行用时: 39ms, 内存消耗: 492K, 提交时间: 2022-08-18 16:46:37

#include<iostream>
#include<cmath>
#include<climits>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=5e3+5;
const ll inf=LLONG_MAX;
PII p[N],q[N];
double dis[N];
bool vis[N];
int n,m;
 
double get_dis(PII a,PII b)
{
    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
 
 
int main()
{
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    scanf("%d",&m);
    n=a+b+c+d;
    for(int i=1;i<=n;++i)
        scanf("%lld%lld",&p[i].x,&p[i].y);
    for(int i=1;i<=m;++i)
        scanf("%lld%lld",&q[i].x,&q[i].y);
    PII O;
    O.first=0,O.second=0;
    for(int i=1;i<=n;++i)
    {
        dis[i]=get_dis(p[i],O);
        for(int j=1;j<=m;++j)
            dis[i]=min(dis[i],get_dis(p[i],q[j]));
    }
//  for(int i=1;i<=n;++i)
//      printf("%lf ",dis[i]);
//  puts("");
    double res=0;
    for(int t=0;t<n;++t)
    {
        int u=-1;
        for(int i=1;i<=n;++i)
            if(!vis[i]&&(u==-1||dis[u]>dis[i]))
                u=i;
        res+=dis[u];
        vis[u]=1;
        for(int i=1;i<=n;++i)
            dis[i]=min(dis[i],get_dis(p[i],p[u]));
    }
    printf("%lf\n",res);
    return 0;
}

C++ 解法, 执行用时: 44ms, 内存消耗: 484K, 提交时间: 2022-04-01 19:30:02

#include<bits/stdc++.h>
using namespace std;

const int N = 2010;

double dp[N];

int x[N], y[N];
bool vis[N];

double sqr(double x){
  return x * x;
}

int main(){
  int n, m;
  n = m = 0;
  for(int i=0; i<4; ++i){
    scanf("%d", &m);
    n += m;
  }
  scanf("%d", &m);
  for(int i=0; i<n; ++i){
    scanf("%d %d", x+i, y+i);
    dp[i] = sqrt(sqr(x[i]) + sqr(y[i]));
  }
  int a, b;
  for(int i=0; i<m; ++i){
    scanf("%d %d", &a, &b);
    for(int j=0; j<n; ++j){
      dp[j] = min(dp[j], sqrt(sqr(x[j] - a) + sqr(y[j] - b)));
    }
  }

  double ans = 0.0;
  for(int i=0; i<n; ++i){
    int k = -1;
    for(int j=0; j<n; ++j){
      if(!vis[j] && (k == -1 || dp[j] < dp[k])) k = j;
    }
    vis[k] = 1;
    ans += dp[k];
    for(int j=0; j<n; ++j){
      if(!vis[j]) dp[j] = min(dp[j], sqrt(sqr(x[j] - x[k]) + sqr(y[j] - y[k])));
    }
  }
  
  printf("%.8f\n", ans);

  return 0;
}