比赛 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;
}