https://atcoder.jp/contests/abc065/submissions/22580754
- 本当に
本の辺を全て試す必要があるか疑うこと
最小全域木なのでクラスカル法ライブラリを貼りたいが、設問そのままグラフを処理しようとすると
で間に合わない。街1と繋がるべき街は2と3、街4と繋がるべき街は5だが、更に各々の連結成分同士を繋げる（xまたはyの絶対値最小の差なので街3と街5）ことで最小全域木が出来上がる。したがって、本の辺は無駄が多くて実際にはxまたはyの絶対値最小の街同士だけで辺を貼ったグラフで十分。このグラフに対してクラスカル法を実行すれば
で処理できる。
