Discrete Speed

Discrete Speed
ダイクストラのD。
「現在の場所、前にいた場所、速度」のノードでグラフを作りました。

#include<iostream>
#include<cstdio>
#include<queue>
#define rep(i, n) for ( int i = 0; i < n; i++ )
using namespace std;
#define MAX 30
#define VMAX 30
#define INFTY (1 << 21)

class State{
    public:
    int pos, from, v;
    double cost;
    
    State( int pos=0, int from=0, int v=0, double cost=0): pos(pos), from(from), v(v), cost(cost){}

    bool operator < ( const State &s) const{
        return cost > s.cost;
    }
};

int n, m, s, g, D[MAX+1][MAX+1], C[MAX+1][MAX+1];

void dijkstra(){
    priority_queue<State> PQ;
    double cost[MAX][MAX][VMAX+1];
    bool visited[MAX][MAX][VMAX+1]; // pos, from, v

    rep(i, n) rep(j, n) rep(k, VMAX+1) {
        cost[i][j][k] = INFTY;
        visited[i][j][k] = false;
    }

    for ( int v = 0; v < n; v++ ){
        if ( D[s][v] == INFTY ) continue;
        cost[v][s][1] = D[s][v]/1.0;
        PQ.push( State(v, s, 1, D[s][v]/1.0) );
    }

    State u, v;

    while( !PQ.empty() ){
        u = PQ.top(); PQ.pop();
        visited[u.pos][u.from][u.v] = true;
        if ( u.pos == g && u.v == 1 ) {
            printf("%.12lf\n", cost[u.pos][u.from][u.v] );
            return;
        }
        for ( int v = 0; v < n; v++ ){
            if ( D[u.pos][v] == INFTY ) continue;
            for ( int nv = u.v-1; nv <= u.v+1; nv++ ){
                if ( visited[v][u.pos][nv] || nv > C[u.pos][v] || v == u.from ) continue;
                double c = cost[u.pos][u.from][u.v] + 1.0*D[u.pos][v]/nv;
                if ( cost[v][u.pos][nv] > c ){
                    cost[v][u.pos][nv] = c;
                    PQ.push( State(v, u.pos, nv, c) );
                }
            }
        }
    }

    cout << "unreachable" << endl;
}

main(){
    int x, y, d, c;
    while( cin >> n >> m && n  ){
        cin >> s >> g; s--; g--;
        rep(i, n) rep(j, n) { D[i][j] = C[i][j] = INFTY; }
        rep(i, m){
            cin >> x >> y >> d >> c; x--; y--;
            D[x][y] = D[y][x] = d;
            C[x][y] = C[y][x] = c;
        }
        dijkstra();
    }
}