考察
道路閉鎖を逆順に見ると辺追加になる。追加前の全点対最短距離が分かると、新しい最短路は追加辺を使わないか、その無向辺を一方向に一度使う形へ単純化できる。
採用する候補: 最終的に残る辺で Floyd–Warshall を行い、クエリを逆処理して閉鎖辺を追加するたび全距離行列を O(N^2) で更新する。
棄却する候補: 各閉鎖・距離問い合わせ後に Dijkstra 法を最初から実行する。
Q は2×10^5で、問い合わせごとの単一始点最短路でも計算量が過大になる。
先に閉鎖される辺を除いたグラフで APSP を構築する。逆順に type 2 の答えを保存し、type 1 では対応辺を追加して旧距離行列を参照しながら全 x,y を更新する。最後に答えを反転する。
典型の発動条件
削除クエリの逆順処理
発動条件: オフラインで削除だけが起こり、逆にすると追加情報を単調に維持できるとき。
道路閉鎖を辺追加へ変換する。
一辺追加時の APSP 更新
発動条件: 全点対距離が既知の無向グラフへ一辺だけ追加するとき。
新辺を一度使う二方向の経路で全 pair を更新する。
問題固有の要素
動的最短路を一般形で解かず、更新回数が300以下という制約と逆順追加を組み合わせる。
別の問題へ持ち帰る視点: 正重みなので新辺を二度以上使う最短路は不要で、旧距離を部品として再利用できる。
正当性
削除は扱いにくいがオフライン逆順なら追加になり、過去の距離は上界としてそのまま利用できる。 辺 (u,v,c) 追加後の dist[x][y] は旧値、dist[x][u]+c+dist[v][y]、dist[x][v]+c+dist[u][y] の最小である。 閉鎖は高々300回で、N≤300 のため O(N^3+TN^2+Q) が許容され、距離問い合わせは O(1) になる。
実装上の注意
- 同じクエリ列で後に再開される辺の初期除外を正確に印付ける。更新中は新値の連鎖を使っても安全だが、十分大きい INF と overflow を管理する。
復習の核
- 追加辺を使う新最短路の三候補を書き、なぜ新辺を複数回通る必要がないかを正重みから説明する。
計算量と制約
時間
O(N³+CN²+Q)、C閉鎖数、reverse辺追加一回O(N²)。
空間
O(N²+M+Q)。
制約との対応
公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 300; 0 \leq M \leq \frac{N(N-1)}{2}; 1 \leq A_i < B_i \leq N; All pairs (A_i, B_i) are distinct.; 1 \leq C_i \leq 10^9; 1 \leq Q \leq 2 \times 10^5; In the queries of the first type, 1 \leq i \leq M.; The road given in a query of the first type is not already closed at that time.; The number of queries of the first type is at most 300.; In the queries of the second type, 1 \leq x < y \leq N.; All input values are integers.
出典