暴力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);
}