1162 - Discrete Speed

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1162

解法

拡張ダイクストラ。
普通のダイクストラはdist[n]を更新することで最短路を求めることができるが、今回は
dist[i][j][k] = スピードkの状態でjからiにつく最短距離
を更新することで最短路を求める。
どこから来たかによってそれぞれ別に考える必要があることに気づかず長時間考えこんでしまった。
もし、
dist[i][k] = スピードkの状態でiにつく最短距離
にしてしまうと、Uターン出来ないという制約によって、dist[i][k]が最短距離という保証が無くなってしまうからである。
以下の実装では、普通にやるとなぜかAOJでTLEになってしまったので、ある程度queueのところでループしたら抜け出すようにした。これで通ってしまったのだが、doubleの精度の問題か何かだろうか・・・。

ソース

struct Edge {
  int src, dst;
  double weight;
  int c;                        // c はグラフでは制限速度、queue では速度
  Edge(int src, int dst, double weight, int c) :
    src(src), dst(dst), weight(weight), c(c){ }
};

bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight :
    e.src != f.src ? e.src < f.src :
    e.dst != f.dst ? e.dst < f.dst : e.c < f.c;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

double dist[30][30][32];           // dist[i][j][k] = スピード k の状態で j から i につく最短距離

double dijkstra(const Graph &g, int s, int t) {
  int n = g.size();
  REP(i,n) REP(j,n) REP(k,32) dist[i][j][k] = INF;
  priority_queue<Edge> Q;
  Q.push(Edge(s,s,0,0));
  int cnt = 0;
  while(!Q.empty()) {
    Edge e = Q.top(); Q.pop();
    if (e.dst == t && e.c == 1) break;
    REP(k,3) {
      int v = e.c - 1 + k;
      if (v<=0) continue;
      if (dist[e.dst][e.src][v] < e.weight) continue;
      FOR(f, g[e.dst]) {
        if (v > f->c) continue;
        if (f->dst == e.src) continue;
        double hoge = e.weight + f->weight / v;
        if (dist[f->dst][f->src][v] > hoge) {
          dist[f->dst][f->src][v] = hoge;
          Q.push(Edge(f->src, f->dst, hoge, v));
        }
      }
    }
    if (cnt++ > 200000) break;  // TLE回避
  }

  double res = INF;
  REP(i,n)
    res = min(res, dist[t][i][1]);
  return res;
}

int main() {
  int n,m;
  while(cin >> n>>m,n||m) {
    int s,t;
    cin >> s >> t;
    s--;t--;
    Graph g(n);
    REP(i,m) {
      int x,y,d,c;
      cin >> x>>y>>d>>c;
      x--;y--;
      g[x].push_back(Edge(x,y,d,c));
      g[y].push_back(Edge(y,x,d,c));
    }
    double res = dijkstra(g,s,t);
    if (res == INF)
      cout << "unreachable" << endl;
    else
      printf("%.5f\n",res);
  }
}