节点数优化dfs,PAC100pts求救
  • 板块P1433 吃奶酪
  • 楼主T7_Daniel
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/25 17:09
  • 上次更新2024/7/25 18:33:41
查看原帖
节点数优化dfs,PAC100pts求救
903392
T7_Daniel楼主2024/7/25 17:09
#include<bits/stdc++.h>
using namespace std;

int n,cnt;
double dis[20][20];
double ans=2E9;
int vis[20];
double t;
struct node{
	double x,y;
}a[20];

double calc(int x,int y){
	double tmp=(a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
	return sqrt(tmp);
}

void solve(){
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			dis[i][j]=calc(i,j);
}
int maxnx=(1<<26)+(1<<23)+(1<<18);
void dfs(int step,int pre,double sum){
	cnt++;
	if(cnt > (maxnx)) return;
	if(step==n+1){
		ans=min(ans,sum);
		return;
	}
	if(ans<sum) return;
	for(int i=1;i<=n;i++){
		if(vis[i]==1) continue;
		vis[i]=1;
		dfs(step+1,i,dis[pre][i]+sum);
		vis[i]=0;
	}
}

signed main(){
	scanf("%d",&n);
	srand(time(0));
	for(int i=1;i<=n;i++)
		scanf("%lf%lf",&a[i].x,&a[i].y);
	//random_shuffle(a+1,a+n+1);
	solve();
	dfs(1,0,0);
	printf("%.2lf",ans);
	return 0;
}
2024/7/25 17:09
加载中...