AcWing 1134. 最短路计数 (bfs代码详解)
原题链接
中等
作者:
Homofrog
,
2021-06-11 22:27:17
,
所有人可见
,
阅读 324
void bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1;
int hh = 0, tt = 0;
q[0] = 1;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + 1) ## 因为dist[j] 初始都为0x3f, 所以如果大于 dist[t] + 1 的话, 则说明是一个新的点, 也就是和上一个点出在同一条路径
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t]; ## 因为同一条路径, 所以cnt不变
q[ ++ tt] = j;
}
else if (dist[j] == dist[t] + 1) ##如果说j 与 t + 1 相等, 则说明dist[j] 之前被其他路径所更新
{
cnt[j] = (cnt[j] + cnt[t]) % mod; ## 此时 dist[j] 应为两条路径数量之和
}
}
}
}