莫名奇妙就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;
}