トヨタ自動車プログラミングコンテスト2022 (AtCoder Beginner Contest 270) F - Transportation (500)
解説の解法
空港、港があるのを島$ n,n+1に辺があるというように実装すると最小全域木で解ける
道路は通常通りに繋げば良い
ただし、空港と港は必須ではないため、それぞれについて使う使わないの4通りで最小全域木を求めてその中の最小コストを答えとする
使わない場合は最小全域木を作るときに辺を見る際に端点のどちらかが$ n,n+1だった場合に飛ばす