畅通工程再续（最小生成树）

#include<stdio.h>
#include<math.h>
#include<string.h>

const int MAXN=1100;
const int INF=0x7fffffff;

struct Node
{
    int x,y;
} node[MAXN*2];

double map[MAXN][MAXN];
int n,flag;
double ans;
int pre[MAXN];
double dist[MAXN];

double _dist(Node a,Node b)
{
    return sqrt((1.0*(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

void Prim()
{
    int i,j,k;
    double mn;
    bool p[MAXN];
    for(i=1; i<=n; i++)
    {
        p[i]=false;
        dist[i]=map[1][i];
        pre[i]=1;
    }
    p[1]=true;
    ans=0;
    for(i=1; i<=n-1; i++)
    {
        mn=INF;
        k=0;
        for(j=1; j<=n; j++)
        {
            if(!p[j] && dist[j]<mn)
            {
                mn=dist[j];
                k=j;
            }
        }
        p[k]=true;
        ans+=dist[k];
        if(k==0)
        {
            flag=1;
            return ;
        }

        for(j=1; j<=n; j++)
        {
            if(!p[j] && map[k][j]!=INF  && dist[j]>map[k][j])
            {
                dist[j]=map[k][j];
                pre[j]=k;
            }
        }
    }
}

int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(i=1; i<=n; i++)
            scanf("%d%d",&node[i].x,&node[i].y);
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                map[i][j]=_dist(node[i],node[j]);
                if(map[i][j]>1000 || map[i][j]<10) map[i][j]=INF;
                if(i==j) map[i][j]=0;
            }
        }
        ans=flag=0;
        Prim();
        if(flag) printf("oh!\n");
        else printf("%.1lf\n",ans*100.0);
    }
    return 0;
}