记录编号	46327	评测结果	AAAAAAAAAA
题目名称	公路修建	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.096 s
提交时间	2012-10-27 15:52:00	内存使用	2.25 MiB

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5000 + 10, INF = 0x7ffffff;
int n;
double x[N], y[N], s, f[N];
bool l[N] = {0};
#define sqr(x) (x)*(x)
inline double dis(int i, int j) {
    return sqrt(sqr(x[i] - x[j]) + sqr(y[i] - y[j]));
}
void Prim() {
    fill(f, f+n, INF);
    f[0] = 0;
    for(int i=0; i<n; i++) {
        double m = INF; int k = 0;
        for(int j=0; j<n; j++) if(!l[j])
            if(f[j] < m) m = f[k = j];
        l[k] = 1;
        for(int j=0; j<n; j++) if(!l[j])
            f[j] = min(f[j], dis(j, k));
    }
}
int main() {
    freopen("roadz.in", "r", stdin);
    freopen("roadz.out", "w", stdout);
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%lf %lf", x+i, y+i);
    Prim();
    for(int i=0; i<n; i++)
        s += f[i];
    printf("%.2lf\n", s);
    return 0;
}