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()