Jumping Hero (UVa Live Archive Europe - Southwestern - 2007/2008 Lisbon (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3984

問題

高さL、幅Cのフィールドの地形とスタート地点、ゴール地点、泉の場所が与えられる。プレイヤーは泉のあるマスに入ると幅NのジャンプをM回しなければならない。ただし、別の泉に入るとその効果は新しい泉の物に上書きされる。また、ジャンプが出来ない場合はその泉に入った場所へと戻される。その条件で、スタート地点からゴール地点まで行くのにかかるの最短時間はいくらか。
L,C<300
2<=M<=6
1<=N<=5
泉の数<=5000

解法

前もって泉を使って移動できる場所を計算してグラフを作っておきダイクストラをする。