SPFA 优化

众所周知，SPFA 它死了

但有些时候你会嫌支持负边的 dijkstra 麻烦，于是不得不选择 SPFA

那么，你需要 SPFA 优化！

SLF 优化

我们可以参考一下 dijkstra 的思路。

dijkstra 每次取队列中的最小值，减少了同一节点入队次数和更新 dis 次数，于是避免了死亡

那么我们感性理解一下，如果我们在 SPFA 中每次也取较小 dis 的点是不是也可以得到一定的优化呢？

我们可以通过双端队列，在节点入队时实现这一点：把需要入队的点的 dis 与队首的比较一下，如果小于队首则将节点从队首入队，否则从队尾入队。

LLL 优化

其实本质原理与 SLF 一样，只是实现方式不同啦 ~

同样使用双端队列，我们额外维护一下队列中所有点的 dis 的平均值，把即将入队的点与这个平均值比较，决定从队首还是队尾入队。

贴（伪）代码

显而易见，这两个优化并不相矛盾，所以我们可以同时使用！

int dis[N];
//起点是 S
inline void SPFA(int S)
{
    //下面这三个东西只在该函数中使用，于是把它们放入函数里，避免被外界调用，不易重名、出错
	static deque<int> q;//双端队列
	static bool inque[N];//记录每个点是否在队列中
	static int sum = 0;//因为平均数不方便维护，我们选择维护队列中 dis 的和
	//TODO: 此处应初始化 dis 数组为 inf
	dis[S] = 0;
	q.push_back(S);
	while (q.size()) {
		int x = q.front();
		q.pop_front();
		inque[x] = 0, sum -= dis[x];//出队维护qaq
		for (/*TODO: 遍历 x 的所有出边： 出边 e 和 对应点 y  */) {
			if (dis[y] > dis[x] + w[e]) {
				dis[y] = dis[x] + w[e];
				if (!inque[y]) {
//此处为两种优化的核心
                    //一定要注意队列为空的特殊情况
					if (q.empty() || dis[y] < dis[q.front()] || dis[y]*q.size() < sum)
						q.push_front(y);
					else q.push_back(y);
//
					inque[y] = 1, sum += dis[y];//入队记得维护qwq
				}
			}
		}
	}
}

十分简单好写呢，为什么不随手写一个呢

注意：LLL 有时可能因为常数问题导致负优化