洛谷P1433 吃奶酪(dfs)
https://www.luogu.com.cn/problem/P1433
运行结果错误,暂不考虑优化,哪里错了,怎么修改
#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
#define N 15
//结构体点
struct P{
P(double x=0,double y=0):x(x),y(y){}
double x,y;
};
//计算两点距离
double getdis(P p1,P p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//全局变量
P ps[N+5];
double ans=10000;
unordered_map<int,int>ind;
//dfs
void dfs(int cnt,P p,float sum ,int n,int t1){
if(cnt==n) {
if(sum<ans) ans=sum;
return;
}
for(int t=t1;t;t-=(-t&t)){
int i=ind[-t&t];
dfs(cnt+1,ps[i],sum+getdis(p,ps[i]),n,t-(1<<i));
}
return;
}
int main(){
int n;
double x,y;
cin>>n;
for(int i=0;i<=n;i++){ //状态压缩:从二进制状态到下标
ind[1<<i]=i;
}
int t=(1<<(n+1))-2;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
ps[i]=P(x,y);
}
ps[0]=P(0,0);
dfs(0,ps[0],0,n,t); //已经吃的奶酪数量,所在点,所走距离,奶酪总数,状态
printf("%.2lf",ans);
}
31行改为t1-