AOJ 2332 - 時空のスゴロク・ロード

時空のスゴロク・ロード
提出コード
すごろく問題です。
すごろく問題なので、ゴールからダイクストラ法を利用してスタート地点に戻りましょう。
まずは下準備をします。
最初に、ある地点からサイコロの目がi(1~6のどれかです)だったときにどこに進むことができるかを調べます。
メモをしつつ埋めていけば、余裕で間に合います。
ループの判定が難しいので、自分は再帰ではなくmapを利用しました。どこかストップできる場所に止まるか、ループになる(すでにmapに追加したものと同じものが存在する)ときに、mapの全ての要素にゴール地点(もしくはループ判定として-2)を記録します。
これが終わったら、ゴールからのルートを探します。
先ほど記録したメモを見て、たどり着く地点から、サイコロを振る地点への有向グラフを作成します。
あとは、作成したグラフをもとにダイクストラ法でスタート地点までさかのぼって行けば完了です。あたりまえですが、メモをしないと、メモリや時間が大変なことになるので気を付けましょう(これを忘れていたのでかなり時間をくいました)。