@[mayike](/user/1039406) 理论上速度快的机子 1s 能跑 $5\times 10^9$，3s 能卡过。
by zengziqvan @ 2024-09-19 22:21:29
@[zengziqvan](/user/935908) 这有点过快了，我本来可以写 floyd 的，结果写了 dij。。
by mayike @ 2024-09-19 22:22:41
@[zengziqvan](/user/935908) 看了一眼最优解，发现我的 dij（在 cf 上）是 140ms，是尼姑最优解！
by mayike @ 2024-09-19 22:24:16
@[zengziqvan](/user/935908) 速度快的机子一般也到不了这个速度；一般认为速度较快的机子可以进行 $10^9$ 左右。
@[mayike](/user/1039406) $n=800$ 过 $\Theta(n^3)$ 倒是并不让人惊讶，1s 擦线跑过去都算是合理的，3s 可以视作是比较稳的过了。
by lsj2009 @ 2024-09-19 22:30:13
@[lsj2009](/user/468657) 谢谢
by mayike @ 2024-09-20 08:10:23