考察
ちょうど k 回移動する最小コスト行列 c^k は、経路を a 歩と b 歩に分けることで min-plus 積 c^a⊗c^b を満たす。
採用する候補: 一歩のコスト行列を min-plus 半環上で二分累乗し、K の立っている bit に対応する行列を min-plus 乗算して c^K を求める。
経路の中継頂点で最小を取る min-plus 積が歩数の加法に対して結合的で、通常の行列累乗と同じ繰り返し二乗が使える。
棄却する候補: 歩数0からKまで dp[step][vertex] を一段ずつ更新する。
K は最大10^9で、各段の N^2 遷移以前に step 数へ比例する処理が不可能である。
(A⊗B)_{i,k}=min_j(A_{i,j}+B_{j,k}) は、前半経路の終点 j を全探索して連結した最小コストである。
単位行列は対角0・非対角∞で、0歩経路を正しく表して累乗 accumulator の初期値になる。
cost を base、min-plus 単位行列を acc とする。K の bit を下から見て、bit が1なら acc=acc⊗base、各段で base=base⊗base と更新し、要求された成分または行列を出力する。
典型の発動条件
min-plus 行列累乗
発動条件: 固定グラフ上で巨大なちょうど K 歩の最短コストを求めるとき。
歩数結合を min-plus 行列積として繰り返し二乗する。
問題固有の要素
通常の和・積を min・加算へ置換しても結合則と単位元があれば、二分累乗の枠組みをそのまま使える。
別の問題へ持ち帰る視点: 巨大回数の同一遷移は、状態間遷移を半環行列として累乗できないか検討する。
正当性
ちょうどa+b歩の任意経路はa歩目の中継点jで一意に分かれる。各jの前後最小値の和をminで取ると全経路の最小値になり、従ってC^{a+b}=C^a⊗C^b。結合則と0歩単位行列により二分累乗はC^Kを正確に計算する。一般の最短路と異なり入力にない待機は追加しない。
実装上の注意
- ∞との加算で overflow しない上限・分岐を設ける。ちょうどK歩なので通常の最短路の0歩待機を勝手に許さない。
復習の核
- 二歩の小例で中継点 j の min-plus 積を手計算し、単位行列と bit 合成が「ちょうど」の歩数を保つことを確認する。
計算量と制約
時間
O(N³ log K)。min-plus行列二分累乗。
空間
O(N²)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 100; 1 \le K \le 10^9; 0 \le C_{i,j} \le 10^9\ (1 \le i \le N,1 \le j \le N); All input values are integers.
出典