AC - 8个点, TLE - 2 个点,怎么优化?
查看原帖
AC - 8个点, TLE - 2 个点,怎么优化?
122342
今夕何年楼主2022/9/10 11:38
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<limits.h>
#include<stack>
#include<cstdlib>

#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define N 5005

using namespace std;

int n;
double dis[N];

struct tp{
	int x,y;
};
tp location[N];

bool vis[N];


double prim(int);

int main()
{
	IOS;
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>location[i].x>>location[i].y; 
	}
	cout<<setiosflags(ios::fixed)<<setprecision(2)<<prim(n);//小数位数为5
	return 0;
} 

double prim(int n)
{
	double ans=0;
	for(int i=1;i<=n;++i)
	{
		dis[i]=double(INF); 
	}
	for(int i=0;i<n;++i)
	{
		int t=-1;
		for(int j=1;j<=n;++j)
			if(!vis[j] && (t==-1||dis[j]<dis[t]))
				t=j;
		if(i)ans+=dis[t];
		vis[t]=true;
		for(int j=1;j<=n;++j)
		{
			double dist=pow(pow(location[j].x-location[t].x,2)+pow(location[j].y-location[t].y,2),0.5);
			dis[j]=min(dis[j],dist);
		}
	}
	return ans;
}
2022/9/10 11:38
加载中...