P1265 公路修建

P1265

#include<bits/stdc++.h>
using namespace std;
int n;
float g[5001][5001];
int x[5001],y[5001];
float minn[5001];
bool check[5001];
float di(int x1,int y1,int x2,int y2){
    return (double)sqrt(1.0*(double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}
int main(){
	//cout<<di(1,1,2,2)<<endl;
	cin>>n;
	memset(g,0x3f,sizeof(g));
	for (int i=1;i<=n;i++)
	    scanf("%d%d",&x[i],&y[i]);
	memset(minn,0x7f,sizeof(minn));
	minn[1]=0;
	memset(check,0,sizeof(check));
	int k=0;
	for (int i=1;i<=n;i++){
	
		int min=0x3f3f3f;
		for (int j=1;j<=n;j++){
			if (!check[j]&&min>minn[j]) 
			    min=minn[j];
			    k=j;
		}
		check[k]=1;
		for (int j=1;j<=n;j++){
			double d=di(x[k],y[k],x[j],y[j]);
			if(d<minn[j])    minn[j]=d;
		}
	}
	double ans=0;
	for (int i=1;i<=n;i++){
		ans+=minn[i];
		//cout<<minn[i]<<" ";
	} 
	printf("%.2lf",ans);
	return 0;
}