算法

\(O(T n \log^2 n)\)

对于 \(\rm{Subtask} \text{ } 1\) , 直接跑 \(n\) 遍 \(\rm{dijkstra}\) 就可以, 这是 \(O(T n ^ 2 \log n)\) 的

对于 \(\rm{Subtask} \text{ } 1\) 的优化:

显然的, 每次 \(\rm{dijkstra}\) 只需要跑到离自己最近的感兴趣的点即可, 因为后面的不可能更优

也行, 但是会被卡

但是思路令人震撼

容易的, 建立超级源点向其中一半的点 (以下记为 \(A\) 集合) 连接一条边权为 \(0\) 的边, 再从另一半 (以下记为 \(B\) 集合) 向超级汇点连接一条边权为 \(0\) 的边, 跑超级源点到超级汇点的最短路

但是这样不一定能解决集合内部双点问题

容易想到随机化选点之后, 多跑几次, 每次成功的几率为 \(\frac{1}{4}\)

随机化 \(20\) 次后, 成功几率达到了 \(99.7\%\) , 包过的啊

考虑正确性做法