AOJ 1162 - 離散的速度

問題
提出コード

解法

都市から都市に速度で移動してきたときにかかる時間の最小値
とすると、現在の都市、1つ前の都市、現在の速度、現在経過した時間をひとまとめにしつつダイクストラをすればこの配列を埋めることができます。
キューから取り出した要素に対して、現在の都市から行くことができる別の都市について、3つの速度パターン(現在の速度に[tex-1,0,1]を加えたもの)を当てはめつつ、経過時間を計算していきます。
答えは、の最小値になります。何か大きな値で初期化をしておき、がどこも更新されていなければ、答えはunreachableとなります。

感想

はじめ、で計算していたため、ある閉路について、時計回りに行くパターンと反時計回りに行くパターンを両方考慮しきれていませんでした。
こういうパターンに素早く気づくことも大切そうです。