Problem:


Problem D: Discrete Speed

Consider car trips in a country where there is no friction.
Cars in this country do not have engines.
Once a car started to move at a speed, it keeps moving at the same speed.
There are acceleration devices on some points on the road,
where a car can increase or decrease its speed by 1.
It can also keep its speed there.
Your job in this problem is to write a program
which determines the route with the shortest time
to travel from a starting city to a goal city.

There are several cities in the country,
and a road network connecting them.
Each city has an acceleration device.
As mentioned above, if a car arrives at a city at a speed v ,
it leaves the city at one of v - 1, v , or v + 1.
The first road leaving the starting city must be run at the speed 1.
Similarly, the last road arriving at the goal city must be run at the speed 1.

The starting city and the goal city are given.
The problem is to find the best route which leads to the goal city
going through several cities on the road network.
When the car arrives at a city, it cannot immediately go back the road
it used to reach the city.  No U-turns are allowed.
Except this constraint, one can choose any route on the road network.
It is allowed to visit the same city or use the same road multiple times.
The starting city and the goal city may be visited during the trip.

For each road on the network, its distance and speed limit are given.
A car must run a road at a speed less than or equal to its speed limit.
The time needed to run a road is the distance divided by the speed.
The time needed within cities including that for acceleration or deceleration should be ignored. 

Input

The input consists of multiple datasets, each in the following format.

n  m 

s  g 

x 1 y 1 d 1 c 1

...

xm  ym  dm  cm 

Every input item in a dataset is a non-negative integer.
Input items in the same line are separated by a space.

The first line gives the size of the road network.
n  is the number of cities in the network.
You can assume that the number of cities is between 2 and 30, inclusive.
m  is the number of roads between cities, which may be zero.

The second line gives the trip.
s  is the city index of the starting city.
g  is the city index of the goal city.
s  is not equal to g .
You can assume that all city indices in a dataset (including the above two)
are between 1 and n , inclusive.

The following m  lines give the details of roads between cities.
The i -th road connects two cities with city indices
xi  and yi ,
and has a distance di  (1 ≤ i ≤ m ).
You can assume that the distance is between 1 and 100, inclusive.
The speed limit of the road is specified by ci .
You can assume that the speed limit is between 1 and 30, inclusive.

No two roads connect the same pair of cities.
A road never connects a city with itself.
Each road can be traveled in both directions.

The last dataset is followed by a line containing two zeros
(separated by a space).

Output

 
For each dataset in the input, one line should be output as specified below.
An output line should not contain extra characters such as spaces.

If one can travel from the starting city to the goal city,
the time needed for the best route (a route with the shortest time)
should be printed.
The answer should not have an error greater than 0.001.
You may output any number of digits after the decimal point,
provided that the above accuracy condition is satisfied.

If it is impossible to reach the goal city,
the string "unreachable" should be printed.
Note that all the letters of "unreachable" are in lowercase.

Sample Input

2 0
1 2
5 4
1 5
1 2 1 1
2 3 2 2
3 4 2 2
4 5 1 1
6 6
1 6
1 2 2 1
2 3 2 1
3 6 2 1
1 4 2 30
4 5 3 30
5 6 2 30
6 7
1 6
1 2 1 30
2 3 1 30
3 1 1 30
3 4 100 30
4 5 1 30
5 6 1 30
6 4 1 30
0 0

Output for the Sample Input

unreachable
4.00000
5.50000
11.25664



Sample input:
2 0
1 2
5 4
1 5
1 2 1 1
2 3 2 2
3 4 2 2
4 5 1 1
6 6
1 6
1 2 2 1
2 3 2 1
3 6 2 1
1 4 2 30
4 5 3 30
5 6 2 30
6 7
1 6
1 2 1 30
2 3 1 30
3 1 1 30
3 4 100 30
4 5 1 30
5 6 1 30
6 4 1 30
0 0


Sample output:
unreachable
4.00000
5.50000
11.25664

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))

INF = 50000

N, M = inpl()
while N:
    s, g = inpl()
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, d, c = inpl()
        G[a].append([b, c, d])
        G[b].append([a, c, d])
    DP = [[INF]*(31) for _ in range(N+1)]
    DP[s][1] = 0
    Q = [[0, 0, s]]  # time, speed, where
    while Q:
        t, v, p = heappop(Q)
        if DP[p][v] < t:
            continue
        for q, c, d in G[p]:
            for dv in range(-1, 2):
                nv = v+dv
                if not (0 < nv <= min(30, c)):
                    continue
                nt = t + d/(nv)
                if DP[q][nv] > nt:
                    DP[q][nv] = nt
                    heappush(Q, [nt, nv, q])
    if DP[g][1] == INF:
        print("unreachable")
    else:
        print(DP[g][1])
    N, M = inpl()

Submission status: Wrong Answer

Solution code:
# AOJ 1162: Discrete Speed
# Python3 2018.7.15 bal4u

INF = 0x7fffffff
import heapq
def dijkstra(V, to, start, goal):
	node = [[[INF for k in range(32)] for j in range(V)] for i in range(V)]
	Q = []
	node[start][0][0] = 0
	heapq.heappush(Q, (0, start, 0, 0))
	while Q:
		t, s, v, p = heapq.heappop(Q)
		if s == goal and v == 1: return node[goal][p][v]
		for e, d, c in to[s]:
			if e == p: continue
			for i in range(-1, 2):
				nv = v+i
				if nv > c or nv <= 0: continue
				nt = node[s][p][v]+d/nv
				if nt < node[e][s][nv]:
					node[e][s][nv] = nt
					heapq.heappush(Q, (nt, e, nv, s))
	return -1
	
while True:
	n, m = map(int, input().split())
	if n == 0: break
	s, g = map(int, input().split())
	s -= 1; g -= 1
	to = [[] for i in range(n)]
	for i in range(m):
		x, y, d, c = map(int, input().split())
		x -= 1; y -= 1
		to[x].append((y, d, c))
		to[y].append((x, d, c))
	ans = dijkstra(n, to, s, g)
	print(ans if ans >= 0 else "unreachable")

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq

while True:
  n,m = map(int, raw_input().split())
  if n == 0 and m == 0: break
  s,g = map(int, raw_input().split())
  s -= 1
  g -= 1
  dist = [[10.0**9 for _ in xrange(n)] for _ in xrange(n)]
  limit = [[0.0 for _ in xrange(n)] for _ in xrange(n)]
  mintime = [[10.0**9 for _ in xrange(40)] for _ in xrange(n)]
  for _ in xrange(m):
    x,y,d,c = map(int, raw_input().split())
    x -= 1
    y -= 1
    dist[x][y] = float(d)
    dist[y][x] = float(d)
    limit[x][y] = float(c)
    limit[y][x] = float(c)
  mintime[s][1] = 0.0

# dijkstra
  # dp[i][j][k] : pos i from j with speed k
  isChecked = [[[False for _ in xrange(40)] for _ in xrange(n)] for _ in xrange(n)]
  q = []
  heapq.heappush(q, (0.0, s, -1, 1))
  while len(q) > 0:
    a = heapq.heappop(q)
    time   = a[0]
    pos    = a[1]
    before = a[2]
    speed  = a[3]
    if isChecked[pos][before][speed]: continue
    if speed == 0: continue
    for nxt in xrange(n):
      if nxt == pos or nxt == before or dist[pos][nxt] == 10.0**9 or limit[pos][nxt] < speed: continue
      for k in xrange(-1, 2):
        if speed + k < 0: continue
        if time + dist[pos][nxt] / float(speed) < mintime[nxt][speed + k]:
          mintime[nxt][speed + k] = time + dist[pos][nxt] / float(speed)
          heapq.heappush(q, (mintime[nxt][speed + k], nxt, pos, speed+k))
  if mintime[g][0] == 10.0**9: print 'unreachable'
  else: print mintime[g][0]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

while True:
  n,m = map(int, raw_input().split())
  if n == 0 and m == 0: break
  s,g = map(int, raw_input().split())
  s -= 1
  g -= 1
  dist = [[10.0**9 for _ in xrange(n)] for _ in xrange(n)]
  limit = [[0.0 for _ in xrange(n)] for _ in xrange(n)]
  mintime = [[10.0**9 for _ in xrange(40)] for _ in xrange(n)]
  for _ in xrange(m):
    x,y,d,c = map(int, raw_input().split())
    x -= 1
    y -= 1
    dist[x][y] = float(d)
    dist[y][x] = float(d)
    limit[x][y] = float(c)
    limit[y][x] = float(c)
  mintime[s][1] = 0.0

  q = deque()
  q.appendleft((s, 1))
  while len(q) > 0:
    a = q.popleft()
    if a[1] == 0: continue
    for i in xrange(n):
      if limit[a[0]][i] < a[1]: continue
      for k in xrange(-1, 2):
        if 0 <= a[1] + k and mintime[a[0]][a[1]] + dist[a[0]][i] / a[1] < mintime[i][a[1] + k]:
          mintime[i][a[1] + k] = mintime[a[0]][a[1]] + dist[a[0]][i] / a[1]
          q.appendleft((i, a[1] + k))
  if mintime[g][0] == 10.0**9: print 'unreachable'
  else: print mintime[g][0]

Submission status: Time Limit Exceeded

Solution code:
MAX_SPEED = 30
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = []
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge.append((x - 1, y - 1, d, c))
        edge.append((y - 1, x - 1, d, c))
    INF = float('inf')
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    dist[S][0][S] = 0.0
    while True:
        flag = False
        for x, y, d, c in edge:
            for j in range(min(MAX_SPEED + 1, c + 2)):
                for k in range(N):
                    if k == y or (j <= c and dist[x][j][k] == INF):
                        continue
                    # print(x, y, d, c, j, k, dist[x][j][k])
                    if j > 1 and dist[y][j - 1][x] > dist[x][j][k] + d / (j - 1):
                        dist[y][j - 1][x] = dist[x][j][k] + d / (j - 1)
                        flag = True
                    if 0 < j <= c and dist[y][j][x] > dist[x][j][k] + d / j:
                        dist[y][j][x] = dist[x][j][k] + d / j
                        flag = True
                    if j < c and dist[y][j + 1][x] > dist[x][j][k] + d / (j + 1):
                        dist[y][j + 1][x] = dist[x][j][k] + d / (j + 1)
                        flag = True
        if not flag:
            break
    """
    for i in range(N):
        print(*dist[i], sep='\n')
        print()
    """
    ans = min(dist[G][1][j] for j in range(N))
    print("unreachable" if ans == INF else "{:.20f}".format(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
MAX_SPEED = 30
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = []
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge.append((x - 1, y - 1, d, c))
        edge.append((y - 1, x - 1, d, c))
    INF = float('inf')
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    dist[S][0][S] = Fraction()
    while True:
        flag = False
        for x, y, d, c in edge:
            for j in range(min(MAX_SPEED + 1, c + 2)):
                for k in range(N):
                    if k == y or (j <= c and dist[x][j][k] == INF):
                        continue
                    # print(x, y, d, c, j, k, dist[x][j][k])
                    if j > 1 and dist[y][j - 1][x] > dist[x][j][k] + Fraction(d, j - 1):
                        dist[y][j - 1][x] = dist[x][j][k] + Fraction(d, j - 1)
                        flag = True
                    if 0 < j <= c and dist[y][j][x] > dist[x][j][k] + Fraction(d, j):
                        dist[y][j][x] = dist[x][j][k] + Fraction(d, j)
                        flag = True
                    if j < c and dist[y][j + 1][x] > dist[x][j][k] + Fraction(d, j + 1):
                        dist[y][j + 1][x] = dist[x][j][k] + Fraction(d, j + 1)
                        flag = True
        if not flag:
            break
    """
    for i in range(N):
        print(*dist[i], sep='\n')
        print()
    """
    ans = min(dist[G][1][j] for j in range(N))
    print("unreachable" if ans == INF else "{:.20f}".format(float(ans)))

Submission status: Time Limit Exceeded

Solution code:
from Queue import Queue

while True:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    INF=100000
    Q=Queue()
    s,g=map(int,raw_input().split())
    s,g=s-1,g-1
    D=[[INF]*n for i in range(n)]
    C=[[0]*n for i in range(n)]
    for i in range(n):
        D[i][i]=0
    for i in range(m):
        x,y,d,c=map(int,raw_input().split())
        x,y=x-1,y-1
        D[y][x]=D[x][y]=d
        C[y][x]=C[x][y]=c
        if x==s:
            Q.put((x,y,1,1))
    T=[[INF]*31 for i in range(n)]
    T[s][1]=0.0
    while not Q.empty():
        x,y,v,pv=Q.get()
        if v==0:continue
        if v>C[x][y]:continue
        if T[y][v]>D[x][y]/float(v)+T[x][pv]:
            T[y][v]=D[x][y]/float(v)+T[x][pv]
            for i in range(n):
                if D[y][i]!=INF or D[y][i]!=0 and i!=x:
                    Q.put((y,i,v-1,v))
                    Q.put((y,i,v,v))
                    Q.put((y,i,v+1,v))
    print T[g][1] if T[g][1]!=INF else "unreachable"

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))

INF = 50000

N, M = inpl()
while N:
    s, g = inpl()
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, d, c = inpl()
        G[a].append([b, c, d])
        G[b].append([a, c, d])
    DP =  [[[INF]*(N+1) for _ in range(31)] for _ in range(N+1)]
    DP[s][0][0] = 0
    Q = [[0, 0, s, 0]]  # time, speed, where, pre
    while Q:
        t, v, p, bp = heappop(Q)
        if DP[p][v][bp] < t:
            continue
        for q, c, d in G[p]:
            if q == bp:
                continue

            for dv in range(-1, 2):
                nv = v+dv
                if not (0 < nv <= c):
                    continue
                nt = t + d/(nv)
                if DP[q][nv][p] > nt:
                    DP[q][nv][p] = nt
                    heappush(Q, [nt, nv, q, p])

    ans = min(DP[g][1])
    if ans == INF:
        print("unreachable")
    else:
        print(ans)
    N, M = inpl()

Submission status: Accepted

Solution code:
# AOJ 1162: Discrete Speed
# Python3 2018.7.15 bal4u

INF = 10e8
import heapq

def dijkstra(V, to, start, goal):
	node = [[[INF for k in range(31)] for j in range(V)] for i in range(V)]
	Q = []
	node[start][0][0] = 0
	heapq.heappush(Q, (0, start, -1, 0))
	while Q:
		t, s, p, v = heapq.heappop(Q)
		if s == goal and v == 1: return t
		for e, d, c in to[s]:
			if e == p: continue    # Uターン禁止
			for i in range(-1, 2):
				nv = v+i
				if nv > c or nv <= 0: continue
				nt = t + d/nv
				if nt < node[e][s][nv]:
					node[e][s][nv] = nt
					heapq.heappush(Q, (nt, e, s, nv))
	return -1
	
while True:
	n, m = map(int, input().split())
	if n == 0: break
	s, g = map(int, input().split())
	s -= 1; g -= 1
	to = [[] for i in range(n)]
	for i in range(m):
		x, y, d, c = map(int, input().split())
		x -= 1; y -= 1
		to[x].append((y, d, c))
		to[y].append((x, d, c))
	ans = dijkstra(n, to, s, g)
	print(ans if ans >= 0 else "unreachable")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
while 1:
    n, m = map(int, raw_input().split())
    if n==m==0:
        break
    s, g = map(int, raw_input().split())
    G = [[] for i in xrange(n+1)]
    for i in xrange(m):
        x, y, d, c = map(int, raw_input().split())
        d = float(d)
        G[x].append((y, d, c))
        G[y].append((x, d, c))

    dist = {}
    # (cost, v, prev, speed)
    que = [(0, (s, -1, 1))]
    dist[s, -1, 1] = 0
    ans = 1e18
    while que:
        cost, key = heappop(que)
        if dist[key] < cost:
            continue
        v, prev, sp = key
        for t, d, c in G[v]:
            if t == prev or sp > c:
                continue
            n_cost = cost + d/sp
            for dv in [-1, 0, 1]:
                if not 0 < sp+dv <= 30:
                    continue
                n_key = (t, v, sp+dv)
                if n_cost < dist.get(n_key, 1e18):
                    dist[n_key] = n_cost
                    heappush(que, (n_cost, n_key))
            if t == g and sp==1:
                ans = min(ans, n_cost)
    print "%.10f" % ans if ans < 1e17 else "unreachable"

Submission status: Accepted

Solution code:
import sys
import heapq
if sys.version[0] == '2':
    range, input = xrange, raw_input
MAX_SPEED = 30
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge[x - 1].append((y - 1, d, c))
        edge[y - 1].append((x - 1, d, c))
    INF = float('inf')
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    que = [(0.0, S, 0, S)]
    while que:
        cost, now, v, prev = heapq.heappop(que)
        if cost > dist[now][v][prev]:
            continue
        if now == G and v == 1:
            print("{:.20f}".format(cost))
            break
        dist[now][v][prev] = cost
        for x, d, c in edge[now]:
            if x == prev:
                continue
            if 0 < v <= c and dist[x][v][now] > dist[now][v][prev] + d / v:
                dist[x][v][now] = dist[now][v][prev] + d / v
                heapq.heappush(que, (dist[x][v][now], x, v, now))
            if v < c and dist[x][v + 1][now] > dist[now][v][prev] + d / (v + 1):
                dist[x][v + 1][now] = dist[now][v][prev] + d / (v + 1)
                heapq.heappush(que, (dist[x][v + 1][now], x, v + 1, now))
            if 1 < v <= c + 1 and dist[x][v - 1][now] > dist[now][v][prev] + d / (v - 1):
                dist[x][v - 1][now] = dist[now][v][prev] + d / (v - 1)
                heapq.heappush(que, (dist[x][v - 1][now], x, v - 1, now))
    else:
        print("unreachable")

Submission status: Accepted

Solution code:
import sys
import heapq
if sys.version[0] == '2':
    range, input = xrange, raw_input
MAX_SPEED = 30
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge[x - 1].append((y - 1, d, c))
        edge[y - 1].append((x - 1, d, c))
    INF = 1e18
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    que = [(0.0, S, 0, S)]
    while que:
        cost, now, v, prev = heapq.heappop(que)
        if cost > dist[now][v][prev]:
            continue
        if now == G and v == 1:
            print("{:.20f}".format(cost))
            break
        dist[now][v][prev] = cost
        for x, d, c in edge[now]:
            if x == prev:
                continue
            for dv in (-1, 0, 1):
                nv = v + dv
                if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
                    dist[x][nv][now] = dist[now][v][prev] + d / nv
                    heapq.heappush(que, (dist[x][nv][now], x, nv, now))
    else:
        print("unreachable")

Submission status: Accepted

Solution code:
import sys
import heapq
if sys.version[0] == '2':
    range, input = xrange, raw_input
MAX_SPEED = 30
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge[x - 1].append((y - 1, d, c))
        edge[y - 1].append((x - 1, d, c))
    INF = float('inf')
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    que = [(0.0, S, 0, S)]
    while que:
        cost, now, v, prev = heapq.heappop(que)
        if cost > dist[now][v][prev]:
            continue
        if now == G and v == 1:
            print("{:.20f}".format(cost))
            break
        dist[now][v][prev] = cost
        for x, d, c in edge[now]:
            if x == prev:
                continue
            for dv in (-1, 0, 1):
                nv = v + dv
                if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
                    dist[x][nv][now] = dist[now][v][prev] + d / nv
                    heapq.heappush(que, (dist[x][nv][now], x, nv, now))
    else:
        print("unreachable")

Submission status: Accepted

Solution code:
import sys
import heapq
if sys.version[0] == '2':
    range, input = xrange, raw_input
MAX_SPEED = 30
dvs = (-1, 0, 1)
while True:
    N, M = map(int, input().split())
    if not (N | M):
        break
    S, G = map(lambda x: int(x) - 1, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        x, y, d, c = map(int, input().split())
        edge[x - 1].append((y - 1, d, c))
        edge[y - 1].append((x - 1, d, c))
    INF = 1e9
    dist = [[[INF for _ in range(N)] for _ in range(MAX_SPEED + 1)] for _ in range(N)]
    que = [(0.0, S, 0, S)]
    while que:
        cost, now, v, prev = heapq.heappop(que)
        if cost > dist[now][v][prev]:
            continue
        if now == G and v == 1:
            print("{:.20f}".format(cost))
            break
        dist[now][v][prev] = cost
        for x, d, c in edge[now]:
            if x == prev:
                continue
            for dv in dvs:
                nv = v + dv
                if 0 < nv <= c and dist[x][nv][now] > dist[now][v][prev] + d / nv:
                    dist[x][nv][now] = dist[now][v][prev] + d / nv
                    heapq.heappush(que, (dist[x][nv][now], x, nv, now))
    else:
        print("unreachable")

Submission status: Accepted

Solution code:
def solve():
    import sys
    from heapq import heappush, heappop
    file_input = sys.stdin
    inf = float('inf')
    
    while True:
        n, m = map(int, file_input.readline().split())
        if n == 0:
            break
        
        s, g = map(int, file_input.readline().split())
        
        adj_list = [[] for i in range(n)]
        for i in range(m):
            x, y, d, c = map(int, file_input.readline().split())
            x -= 1
            y -= 1
            adj_list[x].append((y, d, c))
            adj_list[y].append((x, d, c))
        
        # Dijkstra's algorithm
        s -= 1
        g -= 1
        time_rec = [[[inf] * 31 for j in range(n)] for i in range(n)]
        time_rec[s][s][1] = 0
        
        # pq element: (time, current city, previous city, speed)
        pq = [(0, s, s, 0)]
        
        while pq:
            t, c, p, s = heappop(pq)
            
            if time_rec[p][c][s] < t:
                continue
            
            if c == g and s == 1:
                print(t)
                break
            
            for next_city, d, s_limit in adj_list[c]:
                if next_city == p:
                    continue
                
                if s <= 1:
                    lower_limit = 1
                else:
                    lower_limit = s - 1
                    
                for shifted_s in range(lower_limit, s + 2):
                    if shifted_s > s_limit:
                        continue
                    
                    next_t = t + d / shifted_s
                    
                    if time_rec[c][next_city][shifted_s] <= next_t:
                        continue
                    else:
                        heappush(pq, (next_t, next_city, c, shifted_s))
                        time_rec[c][next_city][shifted_s] = next_t
        else:
            print('unreachable')

solve()

Submission status: Accepted

Solution code:
#2006_D
"""
import sys
from collections import defaultdict
def dfs(d,y,x,f):
    global ans
    if d >= 10:
        return
    f_ = defaultdict(int)
    for i in f.keys():
        f_[i] = f[i]
    for t,s in vr[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s-1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vl[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if s == x-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t,s+1,f_)
            f_[(t,s)] = 1
            break

    for t,s in vd[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y+1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t-1,s,f_)
            f_[(t,s)] = 1
            break

    for t,s in vu[(y,x)]:
        if a[t][s] == 3:
            ans = min(ans,d+1)
            break
        elif f[(t,s)]:
            if t == y-1:
                break
            f_[(t,s)] = 0
            dfs(d+1,t+1,s,f_)
            f_[(t,s)] = 1
            break
    return
while 1:
    w,h = map(int, sys.stdin.readline()[:-1].split())
    if w == h == 0:
        break
    a = [list(map(int, sys.stdin.readline()[:-1].split())) for i in range(h)]
    vr = defaultdict(list)
    vl = defaultdict(list)
    vd = defaultdict(list)
    vu = defaultdict(list)
    f = defaultdict(int)
    for y in range(h):
        for x in range(w):
            if a[y][x] == 1:
                f[(y,x)] = 1
            if a[y][x] in [1,3]:
                for x_ in range(x):
                    vr[(y,x_)].append((y,x))
            elif a[y][x] == 2:
                sy,sx = y,x
    for y in range(h):
        for x in range(w)[::-1]:
            if a[y][x] in (1,3):
                for x_ in range(x+1,w):
                    vl[(y,x_)].append((y,x))
    for x in range(w):
        for y in range(h):
            if a[y][x] in (1,3):
                for y_ in range(y):
                    vd[(y_,x)].append((y,x))
    for x in range(w):
        for y in range(h)[::-1]:
            if a[y][x] in (1,3):
                for y_ in range(y+1,h):
                    vu[(y_,x)].append((y,x))
    ind = [[[0]*4 for i in range(w)] for j in range(h)]
    ans = 11
    dfs(0,sy,sx,f)
    ans = ans if ans < 11 else -1
    print(ans)
"""

#2018_D
"""
import sys
from collections import defaultdict
sys.setrecursionlimit(1000000)

def dfs(d,s,l,v,dic):
    s_ = tuple(s)
    if dic[(d,s_)] != None:
        return dic[(d,s_)]
    if d == l:
        dic[(d,s_)] = 1
        for x in s:
            if x > (n>>1):
                dic[(d,s_)] = 0
                return 0
        return 1
    else:
        res = 0
        i,j = v[d]
        if s[i] < (n>>1):
            s[i] += 1
            res += dfs(d+1,s,l,v,dic)
            s[i] -= 1
        if s[j] < (n>>1):
            s[j] += 1
            res += dfs(d+1,s,l,v,dic)
            s[j] -= 1
        dic[(d,s_)] = res
        return res

def solve(n):
    dic = defaultdict(lambda : None)
    m = int(sys.stdin.readline())
    s = [0]*n
    f = [[1]*n for i in range(n)]
    for i in range(n):
        f[i][i] = 0
    for i in range(m):
        x,y = [int(x) for x in sys.stdin.readline().split()]
        x -= 1
        y -= 1
        s[x] += 1
        f[x][y] = 0
        f[y][x] = 0
    v = []
    for i in range(n):
        for j in range(i+1,n):
            if f[i][j]:
                v.append((i,j))
    l = len(v)
    print(dfs(0,s,l,v,dic))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""
#2011_D
"""
import sys
def dfs(s,d,f,v):
    global ans
    if ans == n-n%2:
        return
    if d > ans:
        ans = d
    for i in range(n):
        if s[i] == 0:
            for j in range(i+1,n):
                if s[j] == 0:
                    if f[i] == f[j]:
                        s[i] = -1
                        s[j] = -1
                        for k in v[i]:
                            s[k] -= 1
                        for k in v[j]:
                            s[k] -= 1
                        dfs(s,d+2,f,v)
                        s[i] = 0
                        s[j] = 0
                        for k in v[i]:
                            s[k] += 1
                        for k in v[j]:
                            s[k] += 1

def solve(n):
    p = [[int(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = [[] for i in range(n)]
    f = [0]*n
    s = [0]*n
    for i in range(n):
        x,y,r,f[i] = p[i]
        for j in range(i+1,n):
            xj,yj,rj,c = p[j]
            if (x-xj)**2+(y-yj)**2 < (r+rj)**2:
                v[i].append(j)
                s[j] += 1
    dfs(s,0,f,v)
    print(ans)
while 1:
    n = int(sys.stdin.readline())
    ans = 0
    if n == 0:
        break
    solve(n)
"""

#2003_D
"""
import sys
def root(x,par):
    if par[x] == x:
        return x
    par[x] = root(par[x],par)
    return par[x]

def unite(x,y,par,rank):
    x = root(x,par)
    y = root(y,par)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def solve(n):
    p = [[float(x) for x in sys.stdin.readline().split()] for i in range(n)]
    v = []
    for i in range(n):
        for j in range(i):
            xi,yi,zi,ri = p[i]
            xj,yj,zj,rj = p[j]
            d = max(0,((xi-xj)**2+(yi-yj)**2+(zi-zj)**2)**0.5-(ri+rj))
            v.append((i,j,d))
    par = [i for i in range(n)]
    rank = [0]*n
    v.sort(key = lambda x:x[2])
    ans = 0
    for x,y,d in v:
        if root(x,par) != root(y,par):
            unite(x,y,par,rank)
            ans += d
    print("{:.3f}".format(round(ans,3)))

while 1:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    solve(n)
"""

#2009_D
import sys
from heapq import heappop,heappush
from collections import defaultdict
def solve(n,m):
    s,g = [int(x) for x in sys.stdin.readline().split()]
    s -= 1
    g -= 1
    e = [[] for i in range(n)]
    for i in range(m):
        a,b,d,c = [int(x) for x in sys.stdin.readline().split()]
        a -= 1
        b -= 1
        e[a].append((b,d,c))
        e[b].append((a,d,c))
    dist = defaultdict(lambda : float("inf"))
    dist[(s,0,-1)] = 0
    q = [(0,s,0,-1)]
    while q:
        dx,x,v,p = heappop(q)
        if x == g and v == 1:
            print(dx)
            return
        for i in range(-1,2):
            v_ = v+i
            if v_ < 1 :continue
            for y,d,c in e[x]:
                if p == y:
                    continue
                if v_ > c:
                    continue
                z = d/v_
                if dx+z < dist[(y,v_,x)]:
                    dist[(y,v_,x)] = dx+z
                    heappush(q,(dist[(y,v_,x)],y,v_,x))
    print("unreachable")
    return

while 1:
    n,m = [int(x) for x in sys.stdin.readline().split()]
    if n == 0:
        break
    solve(n,m)