记录编号 |
52412 |
评测结果 |
AAAAAAAAAA |
题目名称 |
公路修建 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
1.363 s |
提交时间 |
2013-02-04 18:15:01 |
内存使用 |
0.31 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
using namespace std;
#define sqr(x) (x)*(x)
class POINT{
public:
double x,y;
}s[5001];
const int SIZE=5011;//顶点数
const double MAX=0xffffff;
int n;
double ans=0;
inline double dis(int i, int j) {
return sqrt(sqr(s[i].x-s[j].x)+sqr(s[i].y-s[j].y));
}
void Prim(int s){
//s是起点,n是顶点数,c是邻接矩阵,f是存放结果的数组
//顶点下标是1~n,而非0~n-1
bool used[SIZE]={0};
double f[SIZE]={0};
int i,sum,min=-1;
for(i=1;i<=n;i++) f[i]=dis(s,i);
used[s]=1,sum=1,f[s]=0;
double temp;
while(sum<n){
min=-1;
for(i=1;i<=n;i++){
if(used[i]) continue;
if(min==-1||f[i]<f[min]) min=i;
}
if(min==-1) break;
sum++;
used[min]=1;
ans+=f[min];
for(i=1;i<=n;i++){
if(used[i]) continue;
temp=dis(min,i);
if(temp<f[i]) f[i]=temp;
}
}
}
int main(){
freopen("roadz.in","r",stdin);
freopen("roadz.out","w",stdout);
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y);
Prim(1);
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
return 0;
}