[ABC319G] Counting Shortest Paths

[ABC319G] Counting Shortest Paths

Atcoder：[ABC319G] Counting Shortest Paths

洛谷：[ABC319G] Counting Shortest Paths

Problem

经典问题：求补图的最短路，边权均为 \(1\)，并顺带求出 \(1 \to n\) 最短路的数量。\(n \le 2 \times 10^5\)。

Solution

每次从队列中把最早遍历到的节点 \(u\) 取出来，更新所有未被遍历并且与 \(u\) 有边相连的节点 \(v\) 的距离：\(d_v = d_u + 1\)，标记 \(v\) 已被遍历，并把 \(v\) 加进队列。由于每个节点只会被遍历到一次，但维护未被遍历的点集以及快速查询 \(u, v\) 是否存在连边需要用到 set，因此求出 \(1\) 到每个点的最短路长度 \(d\) 的时间复杂度是 \(O(n\log{n})\) 的。

求最短路数量就很简单了，记 \(f_u\) 表示 \(1 \to u\) 的最短路数量，按 \(d\) 从小到大遍历点，记 \(s_i\) 表示 \(d\) 数值为 \(i\) 的所有节点的 \(f\) 之和。

则 \(f_u = s_{d_u - 1} - \sum\limits_{v, d_v = d_u - 1, v \text{ is not connected to } u}f_v\)。这部分的时间复杂度也是 \(O(n\log{n})\) 的。

warning：不要同时遍历 set 和删除 set 内的元素。

code ABC319G