复活 SPFA

不知怎么的，就和 SPFA 较上劲了。 毕竟 dij + 堆 的代码略微有点麻烦 首先，普通的 SPFA 肯定会死翘翘的。 ## 优化一： 每次把一个元素加入队列之后，判断如果比队首的元素小，那么交换队首和队尾，取的时候同样可以这样弄一弄。 于是你发现你的代码跑得快了一丢丢。 ## 优化二： 众所周知：有一种排序算法叫做猴子排序。 ~~但这货很垃圾~~，不过也可以用一用。 每次取队首的时候，随机选一些数，并取出最小的。 ~~如果你运气好，那么 luogu 上的板子您就 AC 了~~，本人的“好运”代码跑了两百多毫秒，[评测记录](https://www.luogu.com.cn/record/48450506)。 ## 优化三： 继续搞事情，我们可以先设定一个阈值 B ，并规定每个点的入队次数不能大于 B ，这样跑完一遍 SPFA 后把所有点到起点的距离再按从小到大排序并依次加入队列（如果无法到达，那就不用加入队列），然后再跑一次没有限制的 SPFA 。你会发现这玩意儿跑的超级快。 调整好参数，或者多跑几遍（像模拟退火那样）就好了。[评测记录](https://www.luogu.com.cn/record/48454614) 这东西主要是利用重构加速。暂且叫它**RMF优化**吧 **（Reconfiguration-Minimum-First）~~【版权所有】~~** 于是我又想去做一下全源最短路，直接暴力跑 SPFA，不料竟然 T 了一个点，又去问了一下隔壁的 UNVRS 巨佬（他也在做复活 SPFA 的行动），发现他也挂掉了，但是我们挂的点不一样，嘿嘿…… ## 优化四（UNVRS的做法）： 还是考虑队列方面的问题。 我们每次取的时候如果队尾元素比队首小，那么交换，但我们可不可以把队尾前面几个或者队首后面几个也拿去试试呢？显然可以，于是你的代码又快了不少。 结合一下，对于每个点直接暴力跑 SPFA 就可以了。 更多详见[UNVRS 的复活 SPFA](https://www.luogu.com.cn/blog/UNVRS/SPFA-PMF)，那里比这里更详细吧，那里详解了 **PMF 优化**。 ### 结合完这些做法之后，好像在普通的图上没什么优势，但目前这种做法应该是在负权图上跑得比较优秀吧……（欢迎来 Hack） ## 几道例题： [单源最短路（标准版）](https://www.luogu.com.cn/problem/P4779)：这个不用说了，随便搞搞就行。 [Johnson全源最短路](https://www.luogu.com.cn/problem/P5905)：用 PMF 和 RMF 优化直接跑过。 [[USACO11JAN]Roads and Planes G](https://www.luogu.com.cn/problem/P3008)：稍微有点烦，不过调调参也可以卡过去，听说 SLF 优化的都直接过了……