原题链接

题解

1.每个城市选择一个与它最近的城市
2.如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
但是这条不成立，请看这条题解
或者下图

由此得出这题就是最小生成树，虽略有不同，注意模拟细节

code

#include<bits/stdc++.h>
using namespace std;
struct node
{
    double x,y;
}poi[5005];

double dist(int i,int j)
{
    return sqrt((poi[i].x-poi[j].x)*(poi[i].x-poi[j].x)+(poi[i].y-poi[j].y)*(poi[i].y-poi[j].y));
}

double dis[5005];
int vis[5005]={0};
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>poi[i].x>>poi[i].y;
    }

    for(int i=1;i<=n;i++) dis[i]=dist(1,i);//初始设点
    vis[1]=1;
    double ans=0;
    int cnt=1;
    int now=1;
    for(int cnt=2;cnt<=n;cnt++)
    {
        double mins=2e18;
        int id;
        for(int i=1;i<=n;i++)
        {
            dis[i]=min(dis[i],dist(i,now));
            if(!vis[i]&&dis[i]<mins)//vis避免了dis为0的问题（重点）
            {
                mins=dis[i];
                id=i;
            }
        }
        ans+=mins;
        now=id;
        vis[id]=1;
    }

    printf("%.2lf\n",ans);

    return 0;
}