考虑从 $s,t$ 开始双向 Dijkstra 跑最短路，直到两边经过的点集出现公共点为止，设为 $p$。由于数据随机，所以每个点会等概率地被 $s$ 和 $t$ 增广到，由生日悖论可以得出，此时经过的点的数量是 $O(\sqrt n)$ 级别的。

考虑此时如何统计答案，容易发现会被算进答案的路径形态一定是：$s\to u\to v\to t$，其中 $u,v$ 之间直接由边相连，$u$ 和 $v$ 分别属于刚才的最短路过程中被 $s,t$ 增广到的集合。该结论证明是简单的，因为如果路径形态是 $s\to u\to x\to v\to t$，由最短路过程的性质有 $dist(s,x)\geq dist(s,p),dist(x,t)\geq dist(p,t)$，这样的路径必然是不优的。事实上需要特殊考虑 $s\to p\to t$，不过这是 trivial 的。

此时我们得到了一个 $O(qm\log m/ \sqrt n)$ 的做法。

为了优化掉复杂度中的 $m$，我们对 Dijkstra 应用一个优化：将一个点所有出边按照边权排序，在松弛时不要全部同时加入优先队列，而是当上一条边出队之后再加入下一条边。这样，第一部分的复杂度就变成了 $O(q\sqrt n\log n)$。

对于第二部分，我们枚举路径中的 $u$ 和它的出边，去更新答案，总共需要考虑 $O(m/\sqrt n)$ 条边。但是事实上，我们可以考虑在 $dist(s,u)$ 和 $dist(v,t)$ 中较小的那一侧去枚举。若 $dist(s,u)+e(u,v)+dist(v,t)\geq dist(s,p)+dist(p,t)$，那么这条路径必然不优。所以我们只需要枚举到 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 即可，较小的那一侧是 $t$ 那一侧的情况是对称的。

那么这一部分总共有多少条边呢？感性理解，对于 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 的边中，满足 $e(u,v)\leq \max\{dist(s,p),dist(p,t)\}-dist(s,u)$ 是所有在第一部分最短路过程中被处理过的边，而这两个值域恰是两倍关系，故第二部分的边数也是 $O(\sqrt n)$ 级别的。

这个感性理解事实上有潜在的漏洞，因为涉及到的概率不一定独立。钱哥声称，第二部分的边数的上界为第一部分边数乘 $O(\log n)$，那么第二部分的边数是 $O(\sqrt n\log n)$ 级别的。总时间复杂度是 $O(q\sqrt n\log n)$。

关于这个问题，钱哥有一个绝妙的证明，但是后面忘了。