3 TLE 90分 求助!!!
查看原帖
3 TLE 90分 求助!!!
886055
MoonCake2011楼主2023/1/18 22:07

各位大佬,求求给我修改优化一下.思路是对的 Subtank #0 -> #10
Subtank #1 -> #12 #13

#include<bits/stdc++.h>
using namespace std;
struct pair{
	double x=0,y=0;
}a[30];
bool s[30];
int n;
double ans,minans=INT_MAX;
double dis(double x,double y,double x2,double y2){
	return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
}
long f(int x){
	if(x==1) return 1;
	return x*f(x-1);
}
long C,num;
void dfs(int x,double ds,int d){
	if(num>C) return;
	if(ans>=minans) return;
	if(ds>minans) return;
	if() 
	if(x>n){
		if(ans<minans) minans=ans;
		num++;
		//cout<<ans<<endl;
		return;
	}
	double now_ds;
	int now_d;
	for(int i=1;i<=n;i++){
		if(s[i]==0){
			s[i]=1;
			now_ds=dis(a[d].x,a[d].y,a[i].x,a[i].y);
			now_d=i;
			ans+=now_ds;
			dfs(x+1,now_ds,now_d);
			s[i]=0;
			ans-=now_ds;
			if(x==n) return;
		}
	}
	return;
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	C=f(n);
	if(n==1){
		ans=dis(0,0,a[1].x,a[1].y);
		printf("%.2f",ans);
		return 0;
	}
	else dfs(1,0,0);
	printf("%.2f",minans);
	return 0;
}
2023/1/18 22:07
加载中...