【最短路】关于卡 SPFA

卡 SPFA 的方法：https://www.zhihu.com/question/292283275

这种方法中提到：

其实从原理上分析，所有 spfa 的优化都是为了使队列接近优先队列。然而，我们知道维护一个优先队列在目前来说是需要 log 的复杂度的，所以低于该复杂度的一定能 Hack。

那，这种情况会不会卡到 Dij？如果不会，为啥啊；如果会，那咋办？

另外，谁能简单分析下这几句话是为啥：

如果选手在SPFA加了一些莫名其妙的随机化，是不是就没法在不看代码的前提下卡掉了?

不是

还有：

其实slf这类优化是很危险的，任何在spfa里用奇怪的优先队列代替普通队列的做法都会破坏bellmanford算法的性质，有可能被卡到指数级！可以参考hdu4889（一道卡spfa+slf的题目，30几个点的图就能卡爆）

为啥啊？

提前谢谢回答的个位了/kel

讨论操作