ABC 369 E — Sightseeing Tour

考察

指定橋以外の移動には制約がないので、全頂点pairの通常最短距離を前計算すれば、指定橋間の移動は端点間距離の参照に置き換えられる。

queryで必須な橋は高々5本であり、最適walkはそれらを渡る順列と各橋を渡る向きの全候補から選べる。

採用する候補: 全点対最短距離を前計算し、各queryで必須橋の順列と向きを列挙して接続距離を評価する。

棄却する候補: queryごとに「何本の指定橋を通過済みか」を状態にして元graph上を最短路探索する。

最大3000 queryで大きいgraph探索を繰り返し、K≤5だから可能な小さな順序列挙を活かせない。

Floyd-Warshallでdist[u][v]を全pairについて求める。各queryのK橋indexをpermutationし、各bit maskで端点方向を決め、島1から各橋入口、橋出口から次入口、最後の出口から島Nまでのdistと橋重みを足す。全候補最小を出力する。

典型の発動条件

全点対最短路による経路segment圧縮

発動条件: 多数queryで少数の必須edge・地点を任意順に訪れるとき。

制約のない区間をendpoint間distのlookupへ置き換える。

小Kの順列・向き全探索

発動条件: 必須対象数だけが非常に小さく、順序とorientationが未知なとき。

permutationとbit maskを直積列挙して各固定caseを評価する。

問題固有の要素

元graphの辺数は大きいがN=400なので、query前にmetric closureを作ることでqueryをK個の橋だけの問題にできる。

別の問題へ持ち帰る視点: static graph上の多数routing queryでは、端点候補が小さくなる前にmetric closureを検討する。

正当性

順番と向きをx_1→y_1,...,x_K→y_Kと固定すれば、費用はdist(1,x_1)+Σ(edgeCost+dist(y_i,x_{i+1}))+edgeCost_K+dist(y_K,N)で一意に最小化される。 指定橋は通常移動中に先に通ってもよいが、最適walkで「必須として数える最初の通過順」を選べば列挙候補に含まれ、距離表利用は正当である。 大きいgraph部分を共通距離表へ圧縮し、query固有の組合せは小さいKだけに限定できる。

実装上の注意

  • 平行辺があればdist初期化をminにし、dist[i][i]=0とする。橋重みは順序によらず一度ずつ足し、64 bitでINF加算を避ける。

復習の核

  • K=1で両方向の式を手計算し、開始1・終了Nとの接続を確認する。permutation配列はqueryごとに初期sortして全候補を生成する。

計算量と制約

時間

O(N³+Σ_query K!2ᴷK)、K≤5は指定橋数。

空間

O(N²+M)、距離と辺情報。

制約との対応

公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 400; N-1 \leq M \leq 2 \times 10^5; 1 \leq U_i < V_i \leq N; 1 \leq T_i \leq 10^9; 1 \leq Q \leq 3000; 1 \leq K_i \leq 5; 1 \leq B_{i,1} < B_{i,2} < \cdots < B_{i,K_i} \leq M; All input values are integers.; It is possible to travel between any two islands using some bridges.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Sightseeing Tour の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 候補数を界して全列挙・有限case分解する

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

    主タグ: 有界全列挙・有限case分解

    補助タグ: 最短路モデル

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

    学習の位置

    体系上の位置: 候補数を界して全列挙・有限case分解する

    • 制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。

    先に読む単元:

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

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

    • 探索空間を二つへ分けて照合するmeet-in-the-middle、および再帰部分問題へ分ける分割統治。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題