E - Hit and Away
题目类型
#BFS #多源BFS #最短路 #次短路
解题思路
通过维护最小值、次小值及最小值来源节点，计算次短路径；再从安全节点进行多源 BFS，更新危险节点的最短路径及次短路径
示例代码
python
def helltractor():
n, m = MII()
g = [[] for _ in range(n)]
for _ in range(m):
u, v = GMI()
g[u].append(v)
g[v].append(u)
s = I()
def push(u, v, w):
if dis[u][0] == -1:
dis[u][0] = v
dis[u][1] = w
q.append((u, v, w))
elif dis[u][-1] == -1 and dis[u][0] != v:
dis[u][-1] = w
q.append((u, v, w))
q = deque()
dis = [[-1] * 3 for _ in range(n)]
for i in range(n):
if s[i] == "S":
push(i, i, 0)
while q:
u, v, w = q.popleft()
for to in g[u]:
push(to, v, w + 1)
ans = []
for i in range(n):
if s[i] == "D":
ans.append(dis[i][1] + dis[i][-1])
print("\n".join(map(str, ans)))