AOJ2332 Space-Time Sugoroku Road

問題概要
1~Nのマスとサイコロがある。各マスには数字が書き込まれている。
・ が正数の時、駒をだけ進める。
・ が負数の時、駒をだけ戻す。
・ が0の時、サイコロを振りのいずれかに移動する。

このとき1からNに到達するために必要なサイコロの振る回数は何回か？

考えたこと
説明文通りであるが、無限ループに気を付ける。
サイコロの振ることを重み１、マスによる移動を重み0としたときのダイクストラ法を考える。
各マスを頂点とすると各頂点から出る辺はせいぜい1か6なので十分間に合う。
最短経路を考えることでループを枝刈りできるのもうれしい。

最初、メモ化再帰で通そうとしたがsample12で落ちた。しばらく考えたが分からなかったので諦めた。（ループ判定で引っかかってそう）

ACコード

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
int dist[100010][2];
int P[100010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    int N;
    cin >> N;
    
    REP(i,N) cin >> P[i];
    REP(i,N) dist[i][0] = dist[i][1] = INT_MAX;
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;

    q.push(make_pair(0, make_pair(0, 0)));
    dist[0][0] = 0;

    while(q.size()){

        auto p = q.top();
        q.pop();

        int d = p.first, v = p.second.first;
        int f = p.second.second;

        if(dist[v][f] < d) continue;

        if(f){

            int u = v + P[v];
            if(P[u] == 0){
                if(dist[u][0] > dist[v][1]){
                    dist[u][0] = dist[v][1];
                    q.push(make_pair(dist[u][0], make_pair(u, 0)));
                }
            }else{
                if(dist[u][1] > dist[v][1]) {
                    dist[u][1] = dist[v][1];
                    q.push(make_pair(dist[u][1], make_pair(u, 1)));
                }
            }
        }else{
            for(int i=1; i<=6; i++){
                int u = min(i+v, N-1);

                if(P[u] == 0){
                    if(dist[u][0] > dist[v][0] + 1){
                        dist[u][0] = dist[v][0] + 1;
                        q.push(make_pair(dist[u][0], make_pair(u, 0)));
                    }
                }else{
                    if(dist[u][1] > dist[v][0] + 1) {
                        dist[u][1] = dist[v][0] + 1;
                        q.push(make_pair(dist[u][1], make_pair(u, 1)));
                    }
                }
            }
        }
    }
    cout << min(dist[N-1][0], dist[N-1][1]) << endl;
    return 0;
}