dfs+小剪枝2WA1TLE求助
  • 板块P1433 吃奶酪
  • 楼主焚魂
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/7/5 20:13
  • 上次更新2023/11/4 18:35:06
查看原帖
dfs+小剪枝2WA1TLE求助
206423
焚魂楼主2021/7/5 20:13
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

int n,v[20];
double x[20],y[20],ans = 100000000;

void dfs(double dis,int step,int nx,int ny) {
	if(dis >= ans)
	return;
	if(step >= n) {
//		cout << dis << endl;
		ans = ans < dis?ans:dis;
	}
	for(int i = 1;i <= n;i++) {
		if(!v[i]) {
			v[i] = 1;
			double te = (x[i] - nx) * (x[i] - nx) + (y[i] - ny) * (y[i] - ny);
			dfs(dis + sqrt(te),step+1,x[i],y[i]);
			v[i] = 0;
		}
	}
}

int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;i++) {
		scanf("%lf%lf",&x[i],&y[i]);
	}
	
	dfs(0,0,0,0);
	
	printf("%.2lf",ans);
	
	return 0;
} 
2021/7/5 20:13
加载中...