hdu 1875 暢通工程再續

/* 最小生成樹 只不過需要建圖  小於10或大於1000的邊設為INF，

*/

#include<cstdio>

#include<cstring>
#include<cmath>
#define INF 1<<30
int n,m,vis[110];
double low[110];
double map[110][110];
struct Node
{
    double x,y;
} a[110];
int init()
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            map[i][j] = INF;
    memset(vis,0,sizeof(vis));
}
double dis(int i,int j)
{
    return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
double prim()
{
    double ans=0;
    for(int i = 0; i <= n; i++)
        low[i] = map[1][i];
    vis[1] = 1;
    for(int i = 1; i < n; i++)
    {
        int temp=INF,pos=-1;
        for(int j = 1; j <= n; j++)
            if(temp>low[j]&&!vis[j])
            {
                temp = low[j];
                pos = j;
            }
        if(pos==-1) return -1;
        vis[pos]=1;
        ans+=low[pos];
        for(int j = 1; j <= n; j++)
            if(!vis[j]&&low[j]>map[pos][j])
                low[j] = map[pos][j];
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf %lf",&a[i].x,&a[i].y);
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                if(i==j) map[i][j] = 0;
                else
                {
                    double temp = dis(i,j);
                    if(temp>1000||temp<10)
                        map[i][j] = INF;
                    else map[i][j] = temp*100;
                }
            }
        double res = prim();
        if(res==-1) puts("oh!");
        else printf("%.1lf\n",res);
    }
    return 0;