HDU 1875開通工事再開【Prim】

滞りなく工事を再開する
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16103    Accepted Submission(s): 5000
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
 
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数C(C<=100)であり、小島の個数を表し、次いでCグループの座標であり、各小島の座標を表し、これらの座標は0<=x、y<=1000の整数である.
Output
各入力データのセットは、ブリッジの最小コストを表す行を出力し、結果は小数点以下を保持します.すべてをスムーズにするために工事が実現できない場合は、「oh!」を出力します.
 
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
 
Sample Output
1414.2
oh!
いくつかの島の座標をあげて、2つの島の距離が10~1000メートルの範囲内の島だけがやっと
道路を作る.1メートル当たり100元かかります.問:すべての島を結ぶ道を築くことができますか.出力
道路建設の最小費用.「oh!」を出力できない場合.
構想:主に図を建てる問題で、Primの上で半日悩んで、最後にやっと図を建てる時多く考えさえすれば
はい.図を作るときは、条件を満たすものだけが距離を与えることができます.そうしないとINF(仮定の無限大)になります.
Primが最小生成木を求めたとき、現在のリンク島に最も近い建造条件を満たす道が見つからなかったら、
そのまま「oh!」を出力し、終了します.そうでなければ、最終出力が最小になるまで検索を続けます.

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

struct City
{
    int x;
    int y;
}A[110];

double G[110][110],low[110];

int vis[110];

void Prim(int N)
{
    memset(vis,0,sizeof(vis));
    vis[1] = 1;
    int pos = 1;
    double ans = 0;
    for(int i = 1; i <= N; i++)//   1      
    {
        if(i != pos)
            low[i] = G[pos][i];

    }
    int count = 1;
    for(int i = 1; i < N; i++)
    {
        double Min = 100000000000;
        for(int j = 1; j <= N; j++)//     pos       
        {
            if(!vis[j] && Min > low[j])
            {
                Min = low[j];
                pos = j;
            }
        }
        if(Min < 100000000000)  //   
        {
            ans += Min;
            vis[pos] = 1;
        }
        else                    //   
        {
            printf("oh!
");
            return;
        }
        for(int j = 1; j <= N; j++)     //  pos                       。
        {
            if(!vis[j] && low[j] > G[pos][j])
            {
                low[j] = G[pos][j];
            }
        }
    }
    printf("%.1lf
",ans*100);
}
int main()
{
    int T,N;
    double Dist,x,y;
    cin >> T;
    while(T--)
    {
        cin >> N;
        memset(A,0,sizeof(A));
        for(int i = 1; i <= N; i++)//    G
            for(int j = 1; j <= N; j++)
                G[i][j] = 100000000000;
        for(int i = 1; i <= N; i++)
        {
            cin >> A[i].x >> A[i].y;
        }
        for(int i = 1; i <= N; i++)
        {
            for(int j = i; j <= N; j++)
            {
                if(i == j)//    i i   0
                {
                    G[i][j] = 0.0;
                    continue;
                }
                x = A[i].x-A[j].x;
                y = A[i].y-A[j].y;
                Dist = sqrt(x*x + y*y);
                if(Dist >= 10.0 && Dist <= 1000.0)//        ，     
                    G[i][j] = G[j][i] = Dist;
            }
        }
        Prim(N);
    }

    return 0;
}