原始的primAC了,下面是0分的堆优化:

#include<bits/stdc++.h>
using namespace std;
int n,size,p[5123][2],book[5123],heap[5123],index[5123];
double dis[5123],ans;
double calculate(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
void shift_down(int i)
{
    int L=i*2,R=i*2+1,mini;
    while(1)
    {
        mini=i;
        if(L<=n&&dis[heap[L]]<dis[heap[i]])
            mini=L;
        if(R<=n&&dis[heap[R]]<dis[heap[mini]])
            mini=R;
        if(mini==i)
            break;
        else
        {
            index[heap[i]]=mini;
            index[heap[mini]]=i;
            
            int buf=heap[i];
            heap[i]=heap[mini];
            heap[mini]=buf;
        }
    }
}
void shift_up(int i)
{
    int father=i/2;
    while(father>0)
    {
        if(dis[heap[father]]>dis[heap[i]])
        {
            index[heap[father]]=i;
            index[heap[i]]=father;

            int buf=heap[i];
            heap[i]=heap[father];
            heap[father]=buf;
        }
    }
}
void heap_pop()
{
    heap[1]=heap[size];
    index[heap[1]]=-1;
    index[heap[size]]=1;
    --size;
    shift_down(1);
}
int heap_front()
{
    return heap[1];
}
int main()
{
    cin>>n;
    size=n;
    for(int i=1;i<=n;++i)
    {
        cin>>p[i][0]>>p[i][1];
        index[i]=i;
    }
    index[1]=-1;
    for(int i=2;i<=n;++i)
        dis[i]=calculate(p[1][0],p[1][1],p[i][0],p[i][1]);
     book[1]=1;
    for(int i=n/2;i>=1;--i)//建堆
        shift_down(i);
    int to;
    for(int i=1;i<=n-1;++i)
    {
        to=heap_front();
        book[to]=1;
        heap_pop();
        ans+=dis[to];
        for(int j=1;j<=n;++j)
        {
            double t=calculate(p[to][0],p[to][1],p[j][0],p[j][1]);
            if(!book[j]&&t<dis[j])//尝试更新生成树到点j的距离
            {
                dis[j]=t;
                shift_up(index[j]);
            }
        }
    }
    printf("%.2lf",ans);
    return 0;
}