AOJ 1162 - Discrete Speed

問題概要

N個の都市とM本のエッジがあり、各エッジには距離dと制限速度cが与えられている。出発地sから速度1で出発し、目的地gへ速度1で到達するための最短時間を求めよ。ただし、ある都市に速度vで到達した場合、その都市から次の都市へは速度v-1, v, v+1のいずれかで移動することができるが、移動中のエッジの制限速度を超えてはならない。Uターンは禁止である。同じ都市やエッジに複数回訪れても良く、出発地や目的地も経由しても良い。目的地に到達できない場合は、"unreachable"を出力せよ。

制約

• 2 ≤ N ≤ 30
• 1 ≤ d_i ≤ 100
• 1 ≤ c_i ≤ 30

解法

dijkstra。
Time[今の都市][今の速度][前の都市] := 最短時間。

感想

Uターンの処理をしていたつもりがしていなくてWAを連発してしまった…。

コード

#include <bits/stdc++.h>
  
using namespace std;
  
#define MAX 35
#define INF 1e9
#define F first
#define S second
typedef pair<double,int> pdi;
typedef pair<int,int> pii;
typedef pair<pdi,pii> State;
  
struct Edge{
  int to,d,c;
  Edge(int to,int d,int c) : to(to),d(d),c(c) {}
};
  
int N,M,s,g;
vector<Edge> G[MAX];
  
double dijkstra(){
  priority_queue<State,vector<State>,greater<State> > Q;
  Q.push(State(pdi(0,s),pii(1,N)));
  double Time[MAX][MAX][MAX];
  fill(Time[0][0],Time[0][0]+MAX*MAX*MAX,INF);   
  Time[s][1][N] = 0;
  
  while(!Q.empty()){
    State p = Q.top(); Q.pop();
    int v = p.F.S, vel = p.S.F;
    if(Time[v][vel][p.S.S] < p.F.F) continue;
 
    if(v == g && vel == 1){
      return Time[g][1][p.S.S];
    }
  
    for(int i = 0 ; i < (int)G[v].size() ; i++){
      for(int j = -1 ; j <= 1 ; j++){
        if(vel+j <= 0) continue;
        if(Time[v][vel][p.S.S] == 0 && j){
          continue;
        }
        Edge e = G[v][i];
        if(e.to == p.S.S) continue;
        double t = (double)e.d/(vel+j);
        if(vel+j <= e.c && 
           Time[v][vel][p.S.S] + t < Time[e.to][vel+j][v]){
          Time[e.to][vel+j][v] = Time[v][vel][p.S.S] + t;
          Q.push(State(pdi(Time[e.to][vel+j][v],e.to),pii(vel+j,v)));
        }
      }
    }
  }
  return INF;
}
  
int main(){
  int x,y,d,c;
  while(cin >> N >> M, N){
    for(int i = 0 ; i < MAX ; i++){
      G[i].clear();
    }
    cin >> s >> g; s--; g--;
    for(int i = 0 ; i < M ; i++){
      cin >> x >> y >> d >> c;
      x--; y--;
      G[x].push_back(Edge(y,d,c));
      G[y].push_back(Edge(x,d,c));
    }
    double res = dijkstra();
    if(res == INF){
      cout << "unreachable" << endl;
    }else{
      printf("%.8f\n",res);
    }
  }
  return 0;
}