コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1753 (記事作成時点)
供養
解法
- 点 $N$ までの任意の最短パス $P$ を求め、$P$ を構成する辺を覚えておく
- 除外する辺が $P$ に含まれる場合、その辺を除いたグラフで再計算する
- $P$ の長さは高々 $N - 1$ なので、再計算も高々 $N - 1$ 回
- 除外する辺が $P$ に含まれない場合、$P$ の長さを出力すればよい
実装
計算量は $O(N(N+M))$
公式解説
躓いた点
- 再計算の回数が高々 $N - 1$ 回であることに気づかなかった
