AGC 12 B - Splatter Painting ( BFS )

B: Splatter Painting - AtCoder Grand Contest 012 | AtCoder

題意：
給一張圖，以及 Q 次操作，每次操作將離 u 距離 d 內的所有節點塗色為 c。初始時每個節點顏色為 0。問所有操作結束後，每個節點分別顏色是什麼。

資料規模：
1≦N,M,Q≦1e5
1≦ai,bi,vi≦N
ai≠bi
0≦di≦10
1≦ci≦1e5
di,ci いずれも整数
与えられるグラフに自己ループや多重辺は存在しない

解法：
首先 d 看起來就很有問題。再來可以注意到，如果當前要執行的是一個塗色指令 ( u, d, c )，卻存在一個較晚的塗色指令 ( u, d', c' ) 使得 d' ≥ d，那麼顯然這次的塗色指令完全沒有意義。因此考慮從後面的操作做回來，每次用 BFS 更新，但只有在這次塗色是有意義 ( 影響力比較晚在同個節點發生的大 ) 的才擴散下去。這個做法的時間複雜度的保證是基於每個節點上的影響力至多只會上升 10 次，也就是狀態一共只有 10 * N 種。
一開始用 Queue() 這東西結果慘 TLE。沒想到 collections.deque() 竟然還比較快...
說是比較快，還是輕鬆慢了 C++ 十倍以上。

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

from collections import deque

N, M = map( int, input().split() )

G = [ [] for i in range( N ) ]
for i in range( M ):
  u, v = map( int, input().split() )
  G[ u - 1 ].append( v - 1 )
  G[ v - 1 ].append( u - 1 )

Q = int( input() )
V = []
D = []
C = []
for qi in range( Q ):
  v, d, c = map( int, input().split() )
  V.append( v - 1 )
  D.append( d )
  C.append( c )

vis = [ -1 for i in range( N ) ]
col = [ 0 for i in range( N ) ]
for qi in range( Q - 1, -1, -1 ):
  if D[ qi ] <= vis[ V[ qi ] ]: continue # 影響力不足
  que = deque()
  vis[ V[ qi ] ] = D[ qi ]
  que.append( ( D[ qi ], V[ qi ] ) )
  if col[ V[ qi ] ] == 0:
    col[ V[ qi ] ] = C[ qi ]
  while len( que ):
    d, u = que.popleft()
    if d == 0: continue
    for v in G[ u ]:
      if vis[ v ] >= d - 1: continue
      vis[ v ] = d - 1
      que.append( ( d - 1, v ) )
      if col[ v ] == 0:
        col[ v ] = C[ qi ]

for i in range( N ):
  print( col[ i ] )