@[JuRuoOIer](/user/476093) 实锤了，dp初始值不够大
by ljlbj_fengyuwuzu @ 2023-11-26 11:56:17
@[JuRuoOIer](/user/476093)
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<cstring>
#include<string>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
using namespace std;
ll n;
lf x[20],y[20],dp[20][(1<<15)+10],ans=0x3f3f3f3f3f3f3f3f;
//dp[s] 为在 s 状态下的最优解
lf getdis(lf a,lf b,lf c,lf d){
return sqrt((c-a)*(c-a)+(d-b)*(d-b));
}
int main(){
memset(dp,127,sizeof(dp));
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
dp[i][(1<<i)]=getdis(0,0,x[i],y[i]);
}
for(int s=1;s<(1<<n);s++){
for(int i=0;i<n;i++){
if(!(s&(1<<i)))continue;
for(int j=0;j<n;j++){
if(i==j||(!(s&(1<<j))))continue;
dp[i][s]=min(dp[i][s],dp[j][s-(1<<i)]+getdis(x[i],y[i],x[j],y[j]));
}
}
}
for(int i=0;i<n;i++){
ans=min(ans,dp[i][(1<<n)-1]);
}
printf("%.2lf",ans);
return 0;
}
```
这样就A了
by ljlbj_fengyuwuzu @ 2023-11-26 11:57:12