color coding と呼ばれる手法を用いてこの問題を解く方法を解説します。

公式解説のような top2 を持つ BFS は一般に実装が複雑になることが多いです。しかし、color coding を用いると計算量は公式解説より劣るものの実装が比較的楽になります。

color coding は以下のようなアルゴリズムです：

• 安全な頂点を \(2\) つのグループにランダムに分ける。
• 各危険な頂点に対しそれぞれの安全な頂点のグループに属する頂点との距離の最小値を求め、暫定的な答えを \(2\) つのグループとのそれぞれの距離の最小値の和で更新する。

上記のアルゴリズムは乱択アルゴリズムですが、このアルゴリズムが成功するときはその危険な頂点から近い top2 の安全な頂点がそれぞれ別のグループに属するときなので \(\displaystyle \frac12\) です。したがって、 \(D\) 回試行して全ての危険な頂点（\(X\) 個とする）に対して正しい答えが求まる確率はおよそ \(\displaystyle \left(1-\frac1{2^D}\right)^X\) であると見積もることができます。この値は \(X=2\times 10^5,D=30\) の場合で \(0.999814\) 程度なので、 \(30\) 回ほど試すことで非常に高い確率で正しい答えを求めることができます。

しかし、上記のアルゴリズムは乱択アルゴリズムで正しい答えが求まらない可能性がありますが、グループ分けを以下のように行うことで脱乱択できます。

• \(k=1,2,\ldots,\lceil \log_2 N\rceil\) に対して以下のようにグループ分けを行う。
  • 頂点番号を二進数で表した時の \(k\) ビット目が \(0\) か \(1\) かでグループ分けし、暫定的な答えを計算する。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(Python3)

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    g[u].append(v)
    g[v].append(u)
s = input()
ok, ng = [], []
for i in range(n):
    if s[i] == "S":
        ok.append(i)
    else:
        ng.append(i)
INF = 10**9


def f(l):
    d = [INF] * n
    q = deque()
    for x in l:
        d[x] = 0
        q.append(x)
    while q:
        x = q.popleft()
        for i in g[x]:
            if d[i] != INF:
                continue
            d[i] = d[x] + 1
            q.append(i)
    return d


ans = [INF] * len(ng)
for k in range(20):
    c1, c2 = [], []
    for x in ok:
        if (x >> k) & 1:
            c2.append(x)
        else:
            c1.append(x)
    d1, d2 = f(c1), f(c2)
    for i in range(len(ng)):
        x = ng[i]
        ans[i] = min(ans[i], d1[x] + d2[x])
for v in ans:
    print(v)