ABC 325 E — Our clients, please wait a moment

考察

carからtrainへは高々1回だけ切り替え、逆は不可なので、routeは「city 1からswitch city iまでcarのみ」+「iからcity Nまでtrainのみ」に分かれる。固定iでの両区間は独立なsingle-mode shortest pathなので、car距離X_iとtrain距離Y_iの和を全iで最小化すればよい。Dは対称なのでi→Nのtrain shortest distanceはN→iと同じweight graphで求められる。carのみでNまで行くcaseはswitch i=N、trainのみはi=1に含まれ、特別caseを別計算する必要がない。complete graphなのでheap版より、未確定最小頂点をarray走査するDijkstraを使えば各modeをO(N^2)で素直に実装できる。

採用する候補: city 1からcar weightのDijkstra、city Nからtrain weightのDijkstraを各1回行い、min_i(X_i+Y_i)を取る。

全switch位置を2本のsingle-source距離arrayで同時評価し、dense graphでもN≤1000の二乗Dijkstraで処理できる。

棄却する候補: 各switch city iごとに前半・後半のshortest pathを別々に解く。

同じmodeの距離計算をN回繰り返し、不要な三次規模になる。

棄却する候補: city 1からi、iからNを直接1 edgeで移動するcostだけ比較する。

Dは三角不等式を保証されず、中間cityを経由した方が短い場合がある。

car graphのedge(i,j)=A·D_{i,j}でsource 1からdense DijkstraしXを得る。train graphのedge(i,j)=B·D_{i,j}+Cでsource Nから同様にYを得る。全i=1..NのX_i+Y_iの最小値を64bit整数で出力する。

典型の発動条件

一方向mode switchの分割

発動条件: mode AからBへ一度だけ切替可能で逆は禁止されるshortest route。

switch頂点前後のsingle-mode距離を足す。

dense graph Dijkstra

発動条件: Nが約1000で全頂点対edge weightが入力matrixからO(1)取得できるとき。

priority queueなしの最小未確定頂点走査でO(N^2)にする。

reverse-source shortest path

発動条件: 各頂点から共通sinkへの距離が必要でedge weightが対称またはreverse graphを作れるとき。

sinkをsourceにした1回の探索で全Y_iを得る。

問題固有の要素

乗換cityを直接列挙してrouteを解く代わりに、全候補へ共有されるcar prefix距離とtrain suffix距離を別々に一括計算できる。

別の問題へ持ち帰る視点: 経路が1つの境界点で2種類へ分かれる問題は、両側の全点距離arrayを前計算してmin-plusで結合する。

正当性

合法routeはcar区間とtrain区間を一つのswitch都市で分割できる。固定switchで両区間は独立だから二つの最短距離和が最適。train距離は対称性で終点から求められ、全switchの最小が全合法routeを覆う。

実装上の注意

  • edge costとpath totalは32bitを超えるため64bit整数と十分大きいINFを使う。
  • trainは移動1回ごとに+Cなので、D_{i,j}B+Cをedge単位で加える。

復習の核

  • Dがmetricでない3-city例を作り、直接edgeより中継が短くなることと、i=1,Nがsingle-mode routeを含むことを確認する。

計算量と制約

時間

都市N、dense complete graph。二回dense Dijkstra O(N²)、switch列挙 O(N)。

空間

入力距離行列 O(N²)、二距離配列 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 1000; 1 \leq A, B, C \leq 10^6; D_{i,j} \leq 10^6; D_{i,i} = 0; D_{i,j} = D_{j,i} > 0 (i \neq j); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Our clients, please wait a moment の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最短路モデル

主題
  • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 最短路モデル

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

      学習の位置

      体系上の位置: 最短路モデル

      • 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

      先に読む単元:

      • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題