90分求调 #10 超时
  • 板块P1433 吃奶酪
  • 楼主YujinSharp
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/28 15:39
  • 上次更新2024/12/28 19:23:26
查看原帖
90分求调 #10 超时
1459579
YujinSharp楼主2024/12/28 15:39

用的dfs,还有什么可以改进的地方吗

#include <bits/stdc++.h>
using namespace std;
const int N=20;
const double mod=1e-2;
int n;
bool xy[N];
double ans=2e9,chess[N][N];
struct chesse {
	double x,y;
} chesse[N];
double len(double x1,double y1,double x2,double y2) {
	double l=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	return l;
}
void memo() {
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=n; j++) {
			if((chess[i][j]==0)&&(i!=j)) {
				double l=len(chesse[i].x,chesse[i].y,chesse[j].x,chesse[j].y);
				chess[i][j]=l;
				chess[j][i]=l;
			}
		}
	}
}
void eat(int ti,int step,double tans) {
	if(step==n+1) {
		ans=min(ans,tans);
		return;
	}
	if(tans-ans>mod) return;
	for(int i=1; i<=n; i++) {
		if(!xy[i]) {
			xy[i]=1;
			double l=chess[i][ti];
			eat(i,step+1,tans+l);
			xy[i]=0;
		}
	}
}
int main() {
	cin>>n;
	chesse[0].x=0;
	chesse[0].y=0;
	for(int i=1; i<=n; i++) {
		cin>>chesse[i].x>>chesse[i].y;
	}
	memo();
	eat(0,1,0);
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}
2024/12/28 15:39
加载中...