关于SPFA，它被我救死了

· · 个人记录

~呜呜呜，我的SPFA又si了~

在spfa优化到AC中，

坏消息：Dep优化属于补救性优化，轻轻一卡就卡掉了，只需要让源点与每个节点连一条边权特别大的边，优化就会失效，就会退化为DFS-spfa（假算法）或普通SPFA加logn常数（如果Dep相同就按广搜序的话...）

好消息：经数学证明，从理论时间复杂度的角度来说，拓扑排序优化属于绝对正优化，并且可以和其他优化配合用！（假如我又弄出一个优化）