ABC218 F - Blocked Roads - かんプリンの学習記録

公式解説より効率の良いアルゴリズムの説明です．

問題概要
解説
関連問題

問題概要

${N}$ 頂点 ${M}$ 辺の有向グラフが与えられる．各 ${i(1\leq i\leq M)}$ について，辺 ${i}$ のみ通れないときの頂点 ${1}$ から頂点 ${N}$ までの最短距離を求めよ．

${2\leq N\leq 400\\ 1\leq M\leq N(N-1)}$

解説

頂点 ${1}$ から頂点 ${N}$ までの最短経路を一つ求めます．明らかに，その最短経路上にない辺を消すときの答えは元のグラフの頂点 ${1}$ から頂点 ${N}$ までの最短距離と一致します．
例えば，下図のグラフにおいて，ある黒の辺を消しても赤の辺からなる最短経路が通れるままなので答えは元のグラフの最短距離になります．
最短経路に含まれる辺の数は高々 ${N-1}$ 本なので，そのような辺ごとにその辺を消したグラフにおける最短距離を求めればいいです．一つの辺につきBFSで ${O(N+M)}$ かかるので全体で ${O(N(N+M))}$ でかかります．

f:id:kanpurin:20210913204907p:plain:w300

最短経路上のある辺 ${(u,v)}$ を消したグラフの最短距離は下図のような位置関係にある頂点 ${t}$ で「頂点 ${1}$ から頂点 ${t}$ を通って頂点 ${N}$ に行くまでの最短距離」のうち最小のものが答えとなります．

f:id:kanpurin:20210913222037p:plain:w300

このとき， ${1\rightarrow L_t\rightarrow t\rightarrow R_t\rightarrow N}$ の順で通るとします． ${L_t,R_t}$ は ${1\rightarrow L_t}$ と ${R_t\rightarrow N}$ は元のグラフの最短経路上の辺を通り， ${L_t\rightarrow t\rightarrow R_t}$ は元のグラフの最短経路上の辺を通らないような頂点とします．各頂点 ${t}$ に対して ${L_t,R_t}$ を計算しておくとこの問題は以下のような問題になります．