AOJ-ICPC - Building a Space Station

問題リンク

どうでもいいのですが、AOJのhttpsのほうを使っていきましょう運動をしています(AOJ-ICPCのリンクがhttpのほうなので仕方ないですが)

解説

AtCoderに似たような発想の問題があった気がします。

球を移動する場合は中心を結んだ線分を通るのが最短です。

よって、2つの球の距離は

あとはこれの最小全域木を求めたらいいので求めることができました！

提出コード

onlinejudge.u-aizu.ac.jp