perogram

D. Edge Deletion ~MSTとDijkstraは似ている?~

MST?

Dijkstra?

Quiz

解説

  • editorialの通り、Dijkstraしつつ辺を追加するごとにカウントアップし、途中で打ち切ればいい

MSTとDijkstraは似ている?

  • 最初、MSTで解くのだと思った。しかしそれは間違い
  • 下記のグラフを考えてみよう

f:id:peroon:20200208044116j:plain

  • Sが始点、Tが終点
  • Tがgood vertexとなるためには、最短距離でつながっている必要があり、Dijkstraが適切
  • エッジの重みが一律1ならば、MSTでもいいだろう

学び

  • MST, Dijkstraは似ているが異なる
  • 最短の条件が出てくるならDijkstraをまず検討