poj---2349---Arctic Network

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include<algorithm>
using namespace std;

const int maxn=11000;
const int INF=0x3f3f3f3f;

double maps[maxn][maxn], dist[maxn];
int vis[maxn];
double a[maxn];
int n, m, k;

void Init()
{
    k=0;
    memset(a, 0, sizeof(a));
    memset(vis, 0, sizeof(vis));

    for(int i=0; i<=n; i++)
    {
        for(int j=0; j<=n; j++)
            maps[i][j]=(i==j)?0:INF;
        dist[i]=INF;
    }
}

int cmp(const void *a, const void *b)
{
    return *(double *)a<*(double *)b?1:-1;
}
void prim()
{
    for(int i=1; i<=n; i++)
        dist[i]=maps[1][i];
    vis[1]=1;

    for(int i=1; i<n; i++)
    {
        double Min=INF;
        int index=-1;

        for(int j=1; j<=n; j++)
        {
            if(!vis[j]&&dist[j]<Min)
            {
                Min=dist[j];
                index=j;
            }
        }

        a[k++]=Min;
        vis[index]=1;

        for(int j=1; j<=n; j++)
            if(!vis[j]&&dist[j]>maps[index][j])
                dist[j]=maps[index][j];

    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &m, &n);
        Init();
        int x[maxn], y[maxn];
        for(int i=1; i<=n; i++)
            scanf("%d %d", &x[i], &y[i]);

        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                maps[i][j]=maps[j][i]=d;
            }
        }

        prim();
        sort(a, a+k);
        printf("%.2f\n", a[k-m]);
    }
    return 0;
}