問題設定
すべての頂点を行き来できる様にすれば良い． 一度つながった辺や円は自由に行き来できるので，connected component の様に考えてよい． 頂点を全て通る様な connected component の作り方が問題になる．
実装
ここで，\(M \leq 8\) と小さいので，そこを利用したい． Connected component で考えたいので， どれを使ったかだけが重要で，使った順番は関係ない． つまり，\(2^M\) で全探索するのが良く，それは間に合う．
前計算として， 頂点同士，頂点と円，円同士を結ぶ道の距離を求めておく． 円同士の距離は，中心同士の距離で場合分け．
公式解説
頂点を半径 \(0\) の円と見ることで，円同士の距離だけに帰着できる． 賢い．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
using P = pair<double,double>;
ll n, m;
cin >> n >> m;
rep(i,n) cin >> p[i].first >> p[i].second;
rep(i,m){
cin >> c[i].first >> c[i].second;
cin >> r[i];
}
auto f = [&](P a, P b) -> double {
return sqrt(square(a.first - b.first) + square(a.second - b.second));
};
auto dis_cir = [&](P c0, double r0, P c1, double r1) -> double {
if(r0 < r1) { // 無いとWA
swap(r0, r1);
swap(c0, c1);
}
double t = f(c0, c1);
if(t >= r0 + r1){
return t - (r0+r1);
}else if(t >= r0 - r1){
return 0;
}else{
return r0 - (r1 + t);
}
};
rep(i,n) rep(j,n) d[i][j] = f(p[i], p[j]);
rep(i,m) rep(j,n) d[i+n][j] = abs(r[i] - f(c[i], p[j]));
rep(i,n) rep(j,m) d[i][j+n] = abs(r[j] - f(c[j], p[i]));
rep(i,m) rep(j,m) d[i+n][j+n] = dis_cir(c[i], r[i], c[j], r[j]);
double ans = 4e18;
rep(s, 1LL<<m){
ll nv = n + pcntll(s);
UnionFind<ll> uf(n+m);
auto ok = [&](ll i) -> bool {
if(in(i,n)) return true;
return s>>(i-n)&1;
};
rep(i, n+m) rep(j, n+m){
if(ok(i) && ok(j)){
ed.push_back({d[i][j], i, j});
}
}
sort(all(ed));
double tmp = 0;
for(auto [co, a, b]: ed){
if(!uf.same(a,b)){
tmp += co;
uf.merge(a,b);
}
}
assert(uf.size(0) == nv);
chmin(ans, tmp);
}
printf("%.10lf", ans);
return 0;
}
