为何WA了一个点??
  • 板块P1433 吃奶酪
  • 楼主LMZYYP
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/10/5 21:38
  • 上次更新2023/11/4 04:40:40
查看原帖
为何WA了一个点??
343319
LMZYYP楼主2021/10/5 21:38

暴力dfs+最优性剪枝,tle的点不说为啥还WA了一个??

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	double x,y;
}a[20];
bool vis[20];
double ans=0x3f3f3f3f;
double sum=0;
double dist(int a,int b,int c,int d){
	return (double)sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
void dfs(int step,int nowx,int nowy){
	if(step==n){
		ans=min(ans,sum);
		return;
	}
	if(sum>ans){
		return;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			sum+=dist(nowx,nowy,a[i].x,a[i].y);
			dfs(step+1,a[i].x,a[i].y);
			vis[i]=0;
			sum-=dist(nowx,nowy,a[i].x,a[i].y);
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&a[i].x,&a[i].y);
	}
	dfs(0,0,0);
	printf("%.2lf",ans);
}
2021/10/5 21:38
加载中...