畅通工程再续 HDU1875

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;

#define maxn 110
#define oo 0x3f3f3f3f
double maps[maxn][maxn], dist[maxn];
int  v[maxn];
int n;

struct node
{
    int x, y;
}s[maxn];

void Init()
{
    int i, j;

    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i==j) maps[i][j]=0;
            else maps[i][j] = maps[j][i] =oo;
        }
    }
}

void Dij()
{
    int flag = 0;
    double sum=0;

    memset(v, 0, sizeof(v));
    for(int i=1; i<=n; i++)
        dist[i] = maps[1][i];
        v[1] = 1;

    for(int i=1; i<n; i++)
    {
        int index;
        double mins = 1000000.0;
        for(int j=1; j<=n; j++)
        {
            if(!v[j] && dist[j]<mins)
            {
                index = j;
                mins = dist[j];
            }
        }

        if(mins == 1000000.0)
        {
           flag = 1;
           break;
        }

        sum += mins;
        v[index] = 1;

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

    if(flag) printf("oh!
");
    else printf("%.1lf
", sum*100);
}
int main()
{
    int T;
    scanf("%d", &T);

    while( T --)
    {
        scanf("%d", &n);

        Init();

        for(int i=1; i<=n; i++)
            scanf("%d %d", &s[i].x, &s[i].y);

        for(int i=1; i<n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                double p = sqrt((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y));
                if(p<10.0 || p>1000.0)
                    continue;
                maps[i][j] = maps[j][i] = min(maps[i][j], p);
            }
        }

        Dij();

    }
    return 0;
}