Submission #70442534

---

Source Code Expand

n, m = map(int, input().split())
G = [set() for _ in range(n)]
for _ in range(m):
  u, v = map(lambda x:int(x)-1, input().split())
  G[u].add(v)
  G[v].add(u)

S = list(input())
S = [s=='S' for s in S]

import heapq
que = []
C1 = [[-1, 1<<60] for _ in range(n)]
C2 = [[-1, 1<<60] for _ in range(n)]

for i in range(n):
  if S[i]:
    heapq.heappush(que, (0, i, i))
    C1[i] = (i, 0)

# print(que)
while que:
  cost, v, fr = heapq.heappop(que)
  if fr not in (C1[v][0], C2[v][0]) or cost not in (C1[v][1], C2[v][1]): 
    continue
  for v_ in G[v]:
    if C2[v_][1]>cost+1 and C1[v_][0]!=fr:
      C2[v_][0] = fr
      C2[v_][1] = cost+1
      if C1[v_][1]>C2[v_][1]:
        C1[v_], C2[v_] = C2[v_], C1[v_]
      heapq.heappush(que, (cost+1, v_, fr))

for i in range(n):
  if not S[i]:
    print(C1[i][1]+C2[i][1])

Submission Info

Judge Result