考察
危険頂点 V を一度訪れて安全頂点から別の安全頂点へ移る最短時間は、V に近い相異なる安全頂点二つまでの距離の和に等しい。全辺重みは 1 なので探索順で近い候補を得られる。経路 U→V→U' は条件を満たし、これより短い経路があれば V までの二つの部分距離の少なくとも一方が二番目に近い安全頂点より短くなるため矛盾する。同じ始点ラベルからの二度目の到達は新しい安全頂点候補にならないので捨て、相異なるラベルだけを各頂点で二つ受理する。
採用する候補: 全安全頂点を同時に始点とし、各状態に始点ラベルを付けた multi-source BFS で各頂点へ異なる二始点からの最短到達を保存する。
各頂点は異なる始点ラベルについて高々二回だけ確定され、全体 O(N+M) で二近傍を得られる。
棄却する候補: 各安全頂点から個別に BFS して全頂点への距離を求める。
安全頂点数に比例して同じ辺を走査し、最悪 O(N(N+M)) になる。
全安全頂点 (u,u,0) をキューへ入れる。状態 (v,source,dist) を取り出し、v がその source を既受理なら無視し、未受理で二件未満なら登録して隣接頂点へ dist+1 を伝播する。各危険頂点の二件の距離を足す。
典型の発動条件
ラベル付き multi-source BFS
発動条件: 複数始点から近い始点を一つでなく上位 k 個求めたいとき。
始点 ID を波面に持たせ、各頂点が異なる二 ID を受理するまで探索を継続する。
k-best 状態の枝刈り
発動条件: 同じ場所への候補が多数あるが、将来必要なのが異なる出所の上位定数個だけのとき。
頂点ごとに二つの始点と距離だけを保存し、それ以降の到達を展開しない。
問題固有の要素
求める往復型経路は V を境に独立な二本の最短路へ分かれ、必要なのは最近傍ではなく相異なる二始点の最近傍である。
別の問題へ持ち帰る視点: multi-source 探索に出所ラベルを残すと、Voronoi の最近傍だけでなく定数個の近傍を線形規模で求められる。
正当性
危険vを通る安全点間walkの費用は二安全点からvまでの距離和の最小で、最短二つの相異なるsourceで達成する。任意点で三番目以降のsourceは既に近い二sourceがあり、その先の同じpathを付けても二候補に負けるので伝播不要。BFSで最短二sourceを確定できる。
実装上の注意
- 同じ安全頂点 source の状態を二回数えない。キューの距離順を保ち、二件確定後の頂点からは不要な三件目を展開しない。
復習の核
- 各頂点の二候補が相異なる安全頂点由来であることと、危険頂点自身の二距離の和が求める経路を構成することを確認する。
計算量と制約
時間
N 頂点、M 辺。各頂点で二sourceを受理するmulti-source BFS O(N+M)。
空間
各点二ラベルと隣接、queue O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3\leq N\leq 2\times 10^5; N-1\leq M\leq 2\times 10^5; 1\leq U_i,V_i\leq N; U_i\neq V_i; If i\neq j, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.; S is a string of length N consisting of S and D.; N,M,U_i,V_i are all integers.; G is connected.; There are at least two safe vertices.; There is at least one dangerous vertex.
出典