ABC065-D Built?
問題
方針
街を頂点、道を辺とみた時の最小全域木が欲しい
任意の2つの街を選んだ場合は$N(N-1)/2$通りある為、 $O(N^2)$となり間に合わない。
$x, y$それぞれでソートを行った時、両隣の要素がそれぞれの街における最短距離の街であるので、これらだけを追加する辺の候補とみなして良い。
街の連結判定はUnionFindを使えば良い(探すのに時間かかった)
計算量は$O(NlogN)$なのでPythonでも十分に間に合う。
感想
やるだけでした
街を頂点、道を辺とみた時の最小全域木が欲しい
任意の2つの街を選んだ場合は$N(N-1)/2$通りある為、 $O(N^2)$となり間に合わない。
$x, y$それぞれでソートを行った時、両隣の要素がそれぞれの街における最短距離の街であるので、これらだけを追加する辺の候補とみなして良い。
街の連結判定はUnionFindを使えば良い(探すのに時間かかった)
計算量は$O(NlogN)$なのでPythonでも十分に間に合う。
やるだけでした