ABC 375 F — Road Blocked

考察

道路閉鎖を逆順に見ると辺追加になる。追加前の全点対最短距離が分かると、新しい最短路は追加辺を使わないか、その無向辺を一方向に一度使う形へ単純化できる。

採用する候補: 最終的に残る辺で 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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Road Blocked の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

主題
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。

    主タグ: 逆向きのオフライン処理

    補助タグ: 最短路モデル

    執筆: abc-explanation-author1.1.1 / revision 1

    学習の位置

    体系上の位置: 時間を逆向きにして未来依存を消す

    • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

    先に読む単元:

    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    この解説で扱わないこと:

    • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題