到达floyd的极限了吗?只能用dij了吗?

P2384 最短路【错题已隐藏】

@[Baiwhiter](/user/127169) 显然 $O(1000^3)$ 是过不了的
by tuxiaobei @ 2020-10-08 16:15:28


@[tuxiaobei](/user/148050) 我记得是能踩线过qwq
by Baiwhiter @ 2020-10-08 16:19:22


$10^9$ 压线过??????????????????????????????????????????????????????????????????????????????????
by 一只书虫仔 @ 2020-10-08 16:22:20


@[Baiwhiter](/user/127169) $O(n^3)$ 1s 应该是过不了的,Floyd 想过 $1000$ 只能在传递闭包问题中使用 `bitset` 优化
by tuxiaobei @ 2020-10-08 16:22:59


@[tuxiaobei](/user/148050) 好的谢谢你
by Baiwhiter @ 2020-10-08 16:25:20


|