RE了9个点,蒟蒻求助!!!
查看原帖
RE了9个点,蒟蒻求助!!!
846041
__xxy_free_ioi__楼主2023/8/2 21:49

莫名奇妙就RE了,也找不出问题。。。

找错找到怀疑人生

#include <bits/stdc++.h>
using namespace std;
struct point{
	double x,y;
	bool visit;
	int num;
} ps[16];
int n;
double ans=DBL_MAX;
double f[16][33000];
double dis(point p1,point p2) {
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void dfs(point p,int step,int mark,double s) {
	if(step==n) {
		if(ans>s) ans=s;
		return;
	}
	for(int i=0;i<n;i++) {
		if(ps[i].visit) continue;
		//剪枝 
		int tmp=mark+1<<i;
		if(f[i][tmp]==0||f[i][tmp]>f[p.num][mark]+dis(ps[i],p)) {
			f[i][tmp]=f[p.num][mark]+dis(ps[i],p);
			ps[i].visit=1;
			dfs(ps[i],step+1,tmp,s+dis(ps[i],p));
			ps[i].visit=0;
		}	
	}
} 
int main(){
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>ps[i].x>>ps[i].y;
		ps[i].visit=0;
		ps[i].num=i;
	}
	point p={0,0,1};
	dfs(p,0,0,0);
	printf("%.2f",ans);
	return 0;
}
2023/8/2 21:49
加载中...