読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

AOJ2332 Space-Time Sugoroku Road(時空のスゴロク・ロード)

Dijkstra AOJ

解法

マスvにいるとき、

  • マス目が0: vからv+1〜v+6マス先まで、コスト1で進める
  • マス目がp(0以外): vからv+pまでコスト0で進める

と考えて、最短距離を求めればよい。

計算量

枝の数がO(V)なので、O(V log V)

コード

ライブラリを貼った

感想

  • ループ判定+BFSでもいけるらしい
    • 最初から気がついていれば実装量的にはそっちのほうが早そう