ABC192 E Train
通常のダイクストラ法を少し拡張する. とはいっても拡張グラフ上でダイクストラ法をするのではなく, 辺の情報に
$ K_i
の情報を付け加える. そしてダイクストラ法のある辺への遷移の際, 移動コストに
$ K_i
の倍数となるまで待つ時間を加えればよい. これで正しく解が求まる. 計算量は
$ O(N \log N)
である.
実装例:
https://atcoder.jp/contests/abc192/submissions/20297467