状態
ブースターは，取る順序は無関係． よって，どれを取ったかの情報だけで済むので，\(2^{M}\)．
頂点も，訪れた順序は無関係で， どれを訪れたかの情報だけで十分なので，\(2^{N}\)． 原点を含めて，\(2^{N+M+1}\) ．
遷移
今の頂点と次の頂点を用いて，\*1;
AtCoder Beginner Contest 274E
};
auto co = [&](ll bm, ll cu, ll ne) -> double {
bm >>= n+1;
int e = pcntll(bm);
double p = 1; rep(i,e) p /= 2.0;
auto [a,b] = v[cu];
auto [c,d] = v[ne];
return dist(a,b,c,d) * p;
};
dp[1LL<<n][n] = 0;
rep(bm,1LL<<k) if(bm){
rep(cu, k) if(bm >> cu & 1) rep(ne,k) if(!(bm >> ne & 1)){
ll nbm = bm | (1LL << ne);
chmin(dp[nbm][ne], dp[bm][cu] + co(bm, cu, ne));
}
}
double ans = 4e18;
rep(bm, 1LL<<k) rep(i,k){
ll s = (1LL << n+1) - 1;
if(((bm & s) == s) && (bm >> i & 1)) {
chmin(ans, dp[bm][i] + co(bm, i, n));
}
}
printf("%.10lf", ans);
return 0;
}
*1:N+M+1)^{2}\).
実装
ハミルトン閉路と同じ．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m ;
cin >> n >> m;
vector<pll> v;
rep(i,n) {
cin >> x[i].first >> x[i].second;
v.push_back(x[i]);
}
v.push_back({0,0});
rep(i,m) {
cin >> p[i].first >> p[i].second;
v.push_back(p[i]);
}
ll k = n+1+m;
auto dist = [&](double a, double b, double c, double d) -> double {
return sqrt(square(c-a) + square(d-b
