AOJ1162.cpp

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (X).begin(),(X).end()

using namespace std;

typedef double Weight;
const Weight INF = 1e10;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
}

void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int n, m, s, g;
int getId(int v, int w, int speed) { return (w - 1) * n * 32 + (v - 1) * 32 + speed; }

int main() {
  while (cin >> n >> m, n) {
    cin >> s >> g;
    Graph G(n * n * 32);
    REP(i,m) {
      int x, y, c;
      double d;
      cin >> x >> y >> d >> c;
      for (int j = 1; j <= n; j++) {
        for (int speed = 1; speed <= c; speed++) {
          if (j != y) {
            add_edge(G, getId(x, j, speed), getId(y, x, speed - 1), d / speed);
            add_edge(G, getId(x, j, speed), getId(y, x, speed + 0), d / speed);
            add_edge(G, getId(x, j, speed), getId(y, x, speed + 1), d / speed);
          }
          if (j != x) {
            add_edge(G, getId(y, j, speed), getId(x, y, speed - 1), d / speed);
            add_edge(G, getId(y, j, speed), getId(x, y, speed + 0), d / speed);
            add_edge(G, getId(y, j, speed), getId(x, y, speed + 1), d / speed);
          }
        }
      }
    }
    Array d;
    dijkstra(G, d, getId(s, s, 1));
    double res = INF;
    for (int j = 1; j <= n; j++) res = min(res, d[getId(g, j, 0)]);
    if (res == INF) cout << "unreachable" << endl;
    else cout << setprecision(10) << fixed << res << endl;
  }
  return 0;
}