MST?
- minimum spanning tree
- 最小全域木のこと
Dijkstra?
Quiz
- Edge Deletion
- https://codeforces.com/contest/1076/problem/D
解説
- editorialの通り、Dijkstraしつつ辺を追加するごとにカウントアップし、途中で打ち切ればいい
MSTとDijkstraは似ている？
- 最初、MSTで解くのだと思った。しかしそれは間違い
- 下記のグラフを考えてみよう
- Sが始点、Tが終点
- Tがgood vertexとなるためには、最短距離でつながっている必要があり、Dijkstraが適切
- エッジの重みが一律１ならば、MSTでもいいだろう
学び
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://images-fe.ssl-images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
