记录编号 52412 评测结果 AAAAAAAAAA
题目名称 公路修建 最终得分 100
用户昵称 Gravatarcstdio 是否通过 通过
代码语言 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;
}