复活 SPFA

不知怎么的，就和 SPFA 较上劲了。

毕竟 dij + 堆 的代码略微有点麻烦

首先，普通的 SPFA 肯定会死翘翘的。

优化一：

每次把一个元素加入队列之后，判断如果比队首的元素小，那么交换队首和队尾，取的时候同样可以这样弄一弄。

于是你发现你的代码跑得快了一丢丢。

优化二：

众所周知：有一种排序算法叫做猴子排序。

但这货很垃圾，不过也可以用一用。

每次取队首的时候，随机选一些数，并取出最小的。

如果你运气好，那么 luogu 上的板子您就 AC 了，本人的“好运”代码跑了两百多毫秒，评测记录。

优化三：

继续搞事情，我们可以先设定一个阈值 B ，并规定每个点的入队次数不能大于 B ，这样跑完一遍 SPFA 后把所有点到起点的距离再按从小到大排序并依次加入队列（如果无法到达，那就不用加入队列），然后再跑一次没有限制的 SPFA 。你会发现这玩意儿跑的超级快。

调整好参数，或者多跑几遍（像模拟退火那样）就好了。评测记录

这东西主要是利用重构加速。暂且叫它RMF优化吧 （Reconfiguration-Minimum-First）【版权所有】

于是我又想去做一下全源最短路，直接暴力跑 SPFA，不料竟然 T 了一个点，又去问了一下隔壁的 UNVRS 巨佬（他也在做复活 SPFA 的行动），发现他也挂掉了，但是我们挂的点不一样，嘿嘿……

优化四（UNVRS的做法）：

还是考虑队列方面的问题。

我们每次取的时候如果队尾元素比队首小，那么交换，但我们可不可以把队尾前面几个或者队首后面几个也拿去试试呢？显然可以，于是你的代码又快了不少。

结合一下，对于每个点直接暴力跑 SPFA 就可以了。

更多详见UNVRS 的复活 SPFA，那里比这里更详细吧，那里详解了 PMF 优化。

结合完这些做法之后，好像在普通的图上没什么优势，但目前这种做法应该是在负权图上跑得比较优秀吧……（欢迎来 Hack）

几道例题：

单源最短路（标准版）：这个不用说了，随便搞搞就行。

Johnson全源最短路：用 PMF 和 RMF 优化直接跑过。

[USACO11JAN]Roads and Planes G：稍微有点烦，不过调调参也可以卡过去，听说 SLF 优化的都直接过了……