ABC 401-500/ABC409F - Connecting Points - 競技プログラミング用 知識集積所

---

問題

ABC409F

必要知識

B以下レベルの内容は省略

• UnionFind木（未作成）
• priority_queue（未作成）

考え方

工夫が必要そうに見えて、実は愚直な実装が正解。
頂点間の距離全パターンを管理することさえできれば、UnionFind木（未作成）を使って指示通りの実装をするだけ。

そして頂点数は最大でも3000なので、全ての点の間の距離は最大で450万。
つまり、priority_queue（未作成）を使えば全ての頂点ペアを距離が短い順に取り出すことは楽勝である。

解答例

解答例

注意点

頂点の追加し忘れに注意

タイプ1のクエリで頂点を追加したとき、既存の頂点一覧に追加し忘れると、追加した頂点同士の距離がpriority_queue（未作成）から漏れてしまう。

別解