geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

スコアを変化させる場合が少ない

ABC218F Blocked Roads

解説なし 辺の距離が全て1なので、最短距離、最短パスはBFSで求まります。 BFSはなので、すべての辺が通れないときを計算すると、で間に合いません。 元のグラフの最短距離が変化するのは、最短パス上の辺が通れなくなった場合だけです。したがって、このと…