10pts,求助
查看原帖
10pts,求助
794093
Brianzhang楼主2024/1/4 21:04
#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[5001];
double dis[5001];
struct point{
	int x,y;
}p[5001];
int main()
{
	int l,a,b;
	double t,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>p[i].x>>p[i].y;
	for(int i=2;i<=n;i++)
	{
		a=abs(p[i].x-p[1].x);
		b=abs(p[i].y-p[1].y);
		t=sqrt(a*a+b*b);
		dis[i]=t;
	}
	vis[1]=1;
	dis[1]=0;
	for(int i=1;i<=n;i++)
	{
		l=1;
		t=1e100;
		for(int j=1;j<=n;j++)
			if(!vis[j]&&dis[j]<t)
			{
				t=dis[j];
				l=j;
			}
		ans+=dis[l];
		vis[l]=1;
		for(int j=1;j<=n;j++)
			if(!vis[j])
			{
				a=abs(p[l].x-p[j].x);
				b=abs(p[l].y-p[j].y);
				t=sqrt(a*a+b*b);
				if(t<dis[j])
					dis[j]=t;
			}
	}
	printf("%.2f",ans);
	return 0;
}
2024/1/4 21:04
加载中...