# GCJ 2017 R1B C. Pony Express ( Floyd Warshall, Dijkstra )

Dashboard - Round 1B 2017 - Google Code Jam

T 筆測資。有 N 個城市，用相鄰矩陣表示距離，不保證輸入距離滿足三角不等式。每個城市有一隻馬，用可行走距離 E 和最高速度 S 描述。Q 筆詢問，問 u 到 v 的最少時間。詢問之間不互相影響，而在一筆詢問中，已捨棄的馬不能再使用。

1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ Ei ≤ 1e9, for all i.
1 ≤ Si ≤ 1000, for all i.
-1 ≤ Dij ≤ 1e9, for all i, j.
Dii = -1, for all i. (There are no direct routes from a city to itself.)
Dij ≠ 0, for all i, j.
Uk ≠ Vk, for all k.
It is guaranteed that the delivery from Uk to Vk can be accomplished with the given horses, for all k.
Ul ≠ Um and/or Vl ≠ Vm, for all different l, m. (No ordered pair of cities to investigate is repeated within a test case.)
1 ≤ Q ≤ 100.
1 ≤ Uk ≤ N, for all k.
1 ≤ Vk ≤ N, for all k.

O( N^3 )

```from queue import PriorityQueue

T = int( input() )
for ti in range( 1, T + 1, 1 ):
N, Q = map( int, input().split() )
E = []
S = []
for i in range( N ):
e, s = map( int, input().split() )
E.append( e )
S.append( s )
adj = [ [] for i in range( N ) ]
for i in range( N ):
adj[ i ] = list( map( int, input().split() ) )
dis = [ [ int( 1e15 ) for i in range( N ) ] for j in range( N ) ]
for i in range( N ):
for j in range( N ):
if adj[ i ][ j ] == -1:
dis[ i ][ j ] = int( 1e15 )
else:
dis[ i ][ j ] = adj[ i ][ j ]
if i == j:
dis[ i ][ j ] = 0
for k in range( N ):
for i in range( N ):
for j in range( N ):
dis[ i ][ j ] = min( dis[ i ][ j ], dis[ i ][ k ] + dis[ k ][ j ] )
ans = []
for qi in range( Q ):
st, ed = map( int, input().split() )
st -= 1
ed -= 1
dp = [ [ 1e15 for i in range( N ) ] for j in range( N ) ]
dp[ st ][ st ] = 0.0
pq = PriorityQueue()
pq.put( [ 0.0, st, st ] )
while not pq.empty():
d, u, h = pq.get()
if dp[ u ][ h ] != d: continue
if u == ed: break
e = E[ h ] - dis[ h ][ u ]
for v in range( N ):
if u == v: continue
if dis[ u ][ v ] > e: continue
if dp[ v ][ h ] > d + dis[ u ][ v ] / S[ h ]:
dp[ v ][ h ] = d + dis[ u ][ v ] / S[ h ]
pq.put( [ dp[ v ][ h ], v, h ] )
if dp[ v ][ v ] > d + dis[ u ][ v ] / S[ h ]:
dp[ v ][ v ] = d + dis[ u ][ v ] / S[ h ]
pq.put( [ dp[ v ][ v ], v, v ] )
ans.append( min( dp[ ed ] ) )
print( "Case #%d: " % ti, end = "" )
for i in range( Q ):
print( "%.7f " % ans[ i ], end = "" )
print()
```