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

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332

解法

マスvにいるとき、

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

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

計算量

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

コード

ライブラリを貼った

感想

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