dfs求调
  • 板块P1433 吃奶酪
  • 楼主yjy_echo
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/11 17:40
  • 上次更新2024/6/11 20:47:13
查看原帖
dfs求调
1192073
yjy_echo楼主2024/6/11 17:40
#include<bits/stdc++.h>
using namespace std;
const int N=20;
double x[N],y[N],t[N][N],ans=1e9+10;
int n,vis[N]={1},sss;
double far(double x1,double x2,double y1,double y2){
//	cout<<1;
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void dfs(int id=0,int s=0,double sum=0){
//	cout<<id<<' '<<s<<' '<<sum<<endl;
    if(s>=ans) return ;
	if(s==n){
		ans=min(ans,sum);
		return ;
	}
	for(int i=0;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i,s+1,sum+t[id][i]);
			vis[i]=0;
		}
	}
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			double m=far(x[i],x[j],y[i],y[j]);
			t[i][j]=m;
		}
	}
	dfs();
	printf("%.2lf",ans); 
	return 0;
}
2024/6/11 17:40
加载中...