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.

解法：
先用 Floyd Warshall 預處理任兩城市之間距離。
對每筆詢問：
進行 dijkstra，節點為 ( u, h )，代表現在在城市 u，騎著的馬是來自城市 h 的。只要有這個狀態，就能求出當前這個馬還可以走多少距離，這個距離顯然是 e[ h ] 減 h 到 u 的最短距離。

時間 / 空間複雜度：
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()