考虑从 s,t 开始双向 Dijkstra 跑最短路,直到两边经过的点集出现公共点为止,设为 p。由于数据随机,所以每个点会等概率地被 s 和 t 增广到,由生日悖论可以得出,此时经过的点的数量是 O(√n) 级别的。
考虑此时如何统计答案,容易发现会被算进答案的路径形态一定是:s→u→v→t,其中 u,v 之间直接由边相连,u 和 v 分别属于刚才的最短路过程中被 s,t 增广到的集合。该结论证明是简单的,因为如果路径形态是 s→u→x→v→t,由最短路过程的性质有 dist(s,x)≥dist(s,p),dist(x,t)≥dist(p,t),这样的路径必然是不优的。事实上需要特殊考虑 s→p→t,不过这是 trivial 的。
此时我们得到了一个 O(qmlogm/√n) 的做法。
为了优化掉复杂度中的 m,我们对 Dijkstra 应用一个优化:将一个点所有出边按照边权排序,在松弛时不要全部同时加入优先队列,而是当上一条边出队之后再加入下一条边。这样,第一部分的复杂度就变成了 O(q√nlogn)。
对于第二部分,我们枚举路径中的 u 和它的出边,去更新答案,总共需要考虑 O(m/√n) 条边。但是事实上,我们可以考虑在 dist(s,u) 和 dist(v,t) 中较小的那一侧去枚举。若 dist(s,u)+e(u,v)+dist(v,t)≥dist(s,p)+dist(p,t),那么这条路径必然不优。所以我们只需要枚举到 e(u,v)≤2(max{dist(s,p),dist(p,t)}−dist(s,u)) 即可,较小的那一侧是 t 那一侧的情况是对称的。
那么这一部分总共有多少条边呢?感性理解,对于 e(u,v)≤2(max{dist(s,p),dist(p,t)}−dist(s,u)) 的边中,满足 e(u,v)≤max{dist(s,p),dist(p,t)}−dist(s,u) 是所有在第一部分最短路过程中被处理过的边,而这两个值域恰是两倍关系,故第二部分的边数也是 O(√n) 级别的。
这个感性理解事实上有潜在的漏洞,因为涉及到的概率不一定独立。钱哥声称,第二部分的边数的上界为第一部分边数乘 O(logn),那么第二部分的边数是 O(√nlogn) 级别的。总时间复杂度是 O(q√nlogn)。
关于这个问题,钱哥有一个绝妙的证明,但是后面忘了。