CSAcademy 23 B. Fast Travel ( Greedy )

題意：
有 N 個城市，以座標描述。兩個城市之間的移動的所需時間是曼哈頓距離。有些城市是特別的 ( S = 1 )，特別的城市之間可以花費 T 單位時間進行瞬間移動。Q 筆詢問，每次問兩個城市之間最少需要花費的移動時間。

限制：
2≤N≤1000
1≤T≤2000
0≤Q≤1000
0≤x,y≤1000
There are no two points that share the same coordinates.

解法：
如果沒有要瞬間移動，那麼顯然直接是兩點的曼哈頓距離。
否則，不會瞬間移動超過一次。枚舉兩者最近的特別的城市作為中繼點更新最小值。

時間 / 空間複雜度：
O( Q * N ) / O( N )

N, T = map( int, input().split() )
S = []
X = []
Y = []
for i in range( N ):
  s, x, y = map( int, input().split() )
  S.append( s )
  X.append( x )
  Y.append( y )
Q = int( input() )
for qi in range( Q ):
  A, B = map( int, input().split() )
  A -= 1
  B -= 1
  ans = abs( X[ A ] - X[ B ] ) + abs( Y[ A ] - Y[ B ] )
  if S[ A ] and S[ B ]:
    ans = min( ans, T )
  mina, minb = int( 1e9 ), int( 1e9 )
  for i in range( N ):
    if not S[ i ]: continue
    if i != A and mina > abs( X[ A ] - X[ i ] ) + abs( Y[ A ] - Y[ i ] ):
      mina = abs( X[ A ] - X[ i ] ) + abs( Y[ A ] - Y[ i ] )
    if i != B and minb > abs( X[ B ] - X[ i ] ) + abs( Y[ B ] - Y[ i ] ):
      minb = abs( X[ B ] - X[ i ] ) + abs( Y[ B ] - Y[ i ] )
  if S[ A ] and not S[ B ]:
    ans = min( ans, T + minb )
  if not S[ A ] and S[ B ]:
    ans = min( ans, T + mina )
  if not S[ A ] and not S[ B ]:
    ans = min( ans, T + mina + minb )
  print( ans )