公式解説より効率の良いアルゴリズムの説明です.
問題はこちら
問題概要
頂点辺の有向グラフが与えられる.各について,辺のみ通れないときの頂点から頂点までの最短距離を求めよ.解説
頂点から頂点までの最短経路を一つ求めます.明らかに,その最短経路上にない辺を消すときの答えは元のグラフの頂点から頂点までの最短距離と一致します.例えば,下図のグラフにおいて,ある黒の辺を消しても赤の辺からなる最短経路が通れるままなので答えは元のグラフの最短距離になります.
最短経路に含まれる辺の数は高々本なので,そのような辺ごとにその辺を消したグラフにおける最短距離を求めればいいです.一つの辺につきBFSでかかるので全体ででかかります.
最短経路上のある辺を消したグラフの最短距離は下図のような位置関係にある頂点で「頂点から頂点を通って頂点に行くまでの最短距離」のうち最小のものが答えとなります.
このとき,の順で通るとします.はとは元のグラフの最短経路上の辺を通り,は元のグラフの最短経路上の辺を通らないような頂点とします.各頂点に対してを計算しておくとこの問題は以下のような問題になります.
これはSegment Treeやstd::setをを用いればで解けます.