G - Road Blocked 2 Editorial
by 
kyopro_friends
都市を頂点、道路を辺としたグラフ \(G=(V,E)\) の問題として考えます。
\(E\) の部分集合 \(E'\) を「頂点 \(1\) から頂点 \(N\) への最短経路に含まれるような辺」からなる集合とします。
\(e=\{u,v\}\) が\(E'\) に属するための必要十分条件は
- (\(1\) から \(u\) までの最短距離) + 辺 \(\{u,v\}\) のコスト + (\(v\) から \(N\) までの最短距離) = (\(1\) から \(N\) までの最短距離)
- (\(1\) から \(v\) までの最短距離) + 辺 \(\{u,v\}\) のコスト + (\(u\) から \(N\) までの最短距離) = (\(1\) から \(N\) までの最短距離)
のどちらかが成り立つことです。頂点 \(1,N\) をそれぞれ始点としたダイクストラ法により各頂点までの最短距離を求めることで、\(O(M\log N)\) で \(E'\) を決定できます。
\(E'\) に含まれない辺に対する答えは明らかに No です。\(E'\) に含まれる辺について考えます。
\(G\) における頂点 \(1\) から頂点 \(i\) への最短距離を \(d_i\) とし、\(G'=(V,E')\) とします。
\((1,\ldots,N)\) の並び替え \(P\) を、\(i<j \implies d_{P_i} \leq d_{P_j}\) を満たすように任意にとります。このとき、\(e=\{u,v\} \in E'\) に対する答えが Yes となるための必要十分条件は、ある \(k\) が存在して、2つの頂点集合 \(S=\{P_1,\ldots,P_k\}\) と \(T=\{P_{k+1},\ldots,P_N\}\) の間を結ぶ \(G'\) の辺が \(e\) のみであることです。
直感的に表現すれば、「\(G'\) の頂点を頂点 \(1\) から近い順に横一列に並べ、適当な箇所で頂点を左右の2つに分けることで、左右をまたぐ辺を \(e\) のみにすることができる」ということです。
証明
分割が存在する ⇒ 答えはYes
$u\in S,v\in T$ として一般性を失わない。 定義から $1=P_1\in S$ であり、$e\in E'$ であることから $d_v\leq d_N$ なので $N\in T$ となる。$(V,E'\setminus\{e\})$ において、$S,T$ は異なる連結成分をなすため、$G'$ において頂点 $1$ から頂点 $N$ へのパスであって$e$ を含まないものは存在しない。$E'$ の定義から、$G$ における頂点 $1$ から頂点 $N$ への最短経路であって $e$ を含まないものは存在しない。分割が存在しない ⇒ 答えはNo
以下の補題が成り立つ。- $G$ における頂点 $1$ から頂点 $N$ への最短経路は、頂点の列が $P$ の部分列となる
補題の証明
任意の $i< j$ に対し、$\{P_i,P_j\}\in E' \implies$ $d_{P_i}+(\text{辺} \{P_i,P_j\} \text{のコスト})=d_{P_j}$ が成り立つことと三角不等式から明らか。必要なら \(u,v\) を入れ替えることで \(u\in S, v\in T\) となるように \(k\) を任意に取る(例えば\(P_k=u\) となるよう取れば良い)。仮定より \(S,T\) をまたぐ辺が \(e\) の他にも存在するため、任意に1つとり \(e'\) とする。\(E'\) の定義から \(G\) における頂点 \(1\) から頂点 \(N\) への最短経路であって \(e'\) を含むものが存在するので任意にとる。補題よりこの最短経路は \(e\) を含まない。
この問題は累積和を用いることで高速に解くことができます。
例 (この例では全ての辺に対する答えが No)：
計算量は全体で \(O(M\log N)\) となります。
このほか、\(E'\) に含まれる辺 \(e\) に対する答えが Yes となるための必要十分条件は、\(G'\) において \(e\) が橋であることであるため、橋を列挙するアルゴリズムを用いることでもこの問題を解くことができます。（上の解説で述べた必要十分条件は「\(e\) が \(G'\) において橋である」より強いですが、実際には単に橋を列挙すれば十分です）
posted:
last update: