求卡常
  • 板块P1433 吃奶酪
  • 楼主BGM114514
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/4 18:44
  • 上次更新2024/8/4 20:06:11
查看原帖
求卡常
705058
BGM114514楼主2024/8/4 18:44
#include<bits/stdc++.h>
using namespace std;
int n;
double x[20],y[20],f[20][20];
struct cheese{
	int now;
	double dis;
	int b;
};
double ans=0x3f3f3f3f;
void dfs(cheese k){
	if(k.dis>=ans)return;
	if(k.b==(1<<(n+1))-1){
		ans=min(ans,k.dis);
		return;
	}
	for(register int i=1;i<=n;i++){
		if(!(k.b&(1<<i))){
			dfs({i,k.dis+f[k.now][i],k.b|(1<<i)});
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			f[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
	}
	dfs({0,0,1});
	printf("%.2f\n",ans);
    return 0;
}
2024/8/4 18:44
加载中...