比赛 |
20110318 |
评测结果 |
MMMMMMMMMM |
题目名称 |
公路修建 |
最终得分 |
0 |
用户昵称 |
王者自由 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-03-18 20:26:22 |
显示代码纯文本
#include <cstdio>
#include <cmath>
#define MAXN 5001
#define INF 2<<15
double ans, G[MAXN][MAXN];
int n, key[MAXN], p[MAXN];
double dis(int x1, int x2, int y1, int y2) {
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void Prim() {
double min, l[MAXN], m[MAXN];
int id;
for(int i=1; i<n; i++) {
l[i] = G[0][i];
m[i] = 0;
}
m[0] = 0;
for(int i=1; i<n; i++) {
min = INF;
id = 0;
for(int j=1; j<n; j++) {
if(l[j]<min && l[j]!=0) {
min = l[j];
id = j;
}
}
ans += min;
l[id] = 0;
for(int j=1; j<n; j++) {
if(G[id][j] < l[j]) {
l[j] = G[id][j];
m[j] = id;
}
}
}
}
int main() {
freopen("roadz.in","r",stdin);
freopen("roadz.out","w",stdout);
int x[MAXN],y[MAXN];
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%d %d", &x[i], &y[i]);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
G[i][j] = dis(x[i],x[j],y[i],y[j]);
Prim();
printf("%.2lf\n", ans);
return 0;
}