记录编号	23775	评测结果	AAAAAAAAAA
题目名称	公路修建	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.945 s
提交时间	2011-03-20 12:55:14	内存使用	0.26 MiB

#include <fstream>
#include <cstdio>
#include <cmath>

using namespace std;

int main ()
{
	ifstream fin("roadz.in");
	FILE *fout = fopen("roadz.out", "w");
	
	int N;
	fin >> N;
	
	bool boo[N];
	double dist[N];
	struct {
		double x, y;
	} city[N];

#define DIST(X,Y) sqrt((city[X].x-city[Y].x)*(city[X].x-city[Y].x)+(city[X].y-city[Y].y)*(city[X].y-city[Y].y))
	for (int i=0; i<N; i++)
	{
		fin >> city[i].x >> city[i].y;
		dist[i] = DIST(i,0);
		boo[i] = false;
	}

	double ans = 0.0;
	for (int i=0; i<N; i++)
	{
		double mp = 100000000.0;
		int k;
		for (int j=0; j<N; j++)
			if (dist[j]<mp && !boo[j])
			{
				k = j;
				mp = dist[j];
			}
			
		boo[k] = true;
		ans += dist[k];
		for (int j=1; j<=N; j++)
		{
			double tp;
			if (!boo[j] && dist[j]>(tp=DIST(k,j)))
				dist[j] = tp;
		}
	}

	fprintf(fout, "%.2f\n", ans);

	fin.close();
	fclose(fout);

	return 0;
}