JOI2020本選4 オリンピックバス 解説
解説
辺 $(u, v)$ を反転させるとき、$(u, v)$ が消えて $(v, u)$ が追加される。 このとき、追加した辺を利用した最短距離は、先にダイクストラ法で前計算しておけば簡単に求められる。 しかし、辺が削除されることには対応できない。
辺が削除されることによって、もともとの $1, N$ の間の最短距離が変化してしまうことが問題なので、言い換えると、$1, N$ 間の最短ルートに、消える辺が含まれる場合が問題である。 このような辺は高々 $O(N)$ 本なので、このような辺を消す場合だけダイクストラ法をやり直して、それ以外の場合は辺の削除を考える必要がなくなって、$O(N(N^2+M))$ でこの問題が解ける。
感想
特殊な制約のときに解法を考えるのが苦手
