「这题用 SPFA 跑最长路的复杂度真的是对的吗」 - 洛谷帖子保存站

这题用 SPFA 跑最长路的复杂度真的是对的吗

板块P3627 [APIO2009] 抢掠计划
楼主Accelessar
当前回复4
已保存回复4
发布时间2023/3/24 21:36
上次更新2023/10/23 20:39:36

被骇客银狼阻止的越权访问保存失败

这题用 SPFA 跑最长路的复杂度真的是对的吗

Accelessar楼主2023/3/24 21:36

如果能把 SPFA 卡到 $O(nm)$ ，那 n,m 范围都在 5e5 是不是会 T

还是说在 DAG 上跑最短（长）路复杂度会小一些？求教

2023/3/24 21:36