比赛 HAOI2009 模拟试题3 评测结果 AAAAAAAAAA
题目名称 公路修建 最终得分 100
用户昵称 TBK 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-28 14:20:01
显示代码纯文本
#include <iostream> 
#include <cstdio> 
#include <cstdlib> 
#include <cmath> 
#include <cstring> 
#include <string> 
#include <iomanip> 
#define MMM 1000000 
#define MAXN 0x7fffffff 
using namespace std; 
int b,c,d,l,n[5000],r[5000][2]={0}; 
double s=0,k,m[5000]; 
bool bo[5000]={false}; 
double ab(double z) 
{ 
    return z>0?z:-z; 
} 
double jisuan(int x,int y) 
{ 
    double p,q; 
    p=fabs((double)(r[x][1]-r[y][1]))*fabs((double)(r[x][1]-r[y][1])); 
    q=fabs((double)(r[x][0]-r[y][0]))*fabs((double)(r[x][0]-r[y][0])); 
    return sqrt(p+q); 
} 
int main(void) 
{ 
    freopen ("roadz.in","r",stdin); 
    freopen ("roadz.out","w",stdout); 
    scanf("%d",&b); 
    for (c=0;c<b;c++)  
    { 
        scanf("%d%d",&r[c][0],&r[c][1]); 
        r[c][0]+=MMM; 
        r[c][1]+=MMM; 
    } 
    bo[0]=true; 
    for(c=1;c<b;c++) 
    { 
       m[c]=jisuan(0,c); 
       n[c]=0; 
    } 
    for (c=1;c<b;c++) 
    { 
        k=MAXN; 
        l=0; 
        for (d=0;d<b;d++) 
            if ((bo[d]==false)&&(m[d]<k)) 
            { 
                k=m[d]; 
                l=d; 
            } 
        s+=m[l]; 
        bo[l]=true; 
        for (d=0;d<b;d++) 
            if ((bo[d]==false)&&(jisuan(d,l)<m[d])) 
            { 
                m[d]=jisuan(d,l); 
                n[d]=l; 
            } 
    } 
    printf("%.2lf",s); 
    fclose(stdin); 
    fclose(stdout); 
    return 0; 
}