本文章将同步分享于luogu

免责申明:本方案不能保证不被卡TLE，后面有时间复杂度证明

壹：思路 & 代码

LLL的扩展优化，听起来有些不靠谱。但其实文章所讲的仅仅只是最基础，最简单的实现方法（也代指思路的不清晰，代码的简单粗暴），并且对稠密图有很大的优化。好了这些都是闲话，后面再说说。

---

大体思路

有一个队列 $Q1$ ，一个栈 $S1$ 。 从 $Q1$ 的队头取出节点开始松弛。

当进入新的节点时，把 $Q1$ 从后往前遍历，比较该节点的距离，如果比新的节点的距离小或等于，停止循环。否则，把该节点放入到 $S1$ 。

最后，将新节点放入到 $Q1$ 的尾部。

当一个节点松弛结束，如果 $Q1$ 为空，就把 $S1$ 的所有节点放入到 $Q1$。

---

Step1

有一个队列 $Q1$ ，一个栈 $S1$ 。

解释：根据上面的大体思路，发现 $Q1$ 近似单调队列（至于为什么是近似，等下你就知道了）。根据操作，单调队列越大的距离越先取出（反之，越小的越后取出），所以选到先进后出的栈。

int q1[M << 1], int s1[M << 1];
int h1 = 1, t1 = 0, t2 = 0;
// Q1的头尾指针，S1的栈顶指针

Step2

从 $Q1$ 的队头取出节点开始松弛。

当进入新的节点时，把 $Q1$ 从后往前遍历，比较该节点的距离。

如果比新的节点的距离小或等于，停止循环;

否则，把该节点放入到 $S1$ 。

最后，将新节点放入到 $Q1$ 的尾部。

// from代指取出的头节点 ,to 代指新节点，dis代指到新节点的距离
for(...){
  if(dist[to] > dist[from] + dis){
     dist[to] = dist[from] + dis;
     // 核心代码：
     while(t1-h1+1 > 0 && dist[q1[t1]] > dist[to]) s1[++t2] = q1[t1--];
    // st数组标记是否在队列里
     if(st[to]) continue;
     st[to] = true;
     q1[++t1] = to;
  }
}

 while(t1-h1+1 > 0 && dist[q1[t1]] > dist[to]) s1[++t2] = q1[t1--];
/*
  解释：首先判断Q1是否为空，如果为空停止循环
  然后，判断Q1尾部节点的距离是否大于新节点的距离。
  如果大于，那么将Q1尾部节点放入S1。
  否则，停止循环。
*/

Step3

当一个节点松弛结束，如果 $Q1$ 为空，就把 $S1$ 的所有节点放入到 $Q1$ 。

这里确实我想只把 $S1$ 的栈顶元素放入 $Q1$ 的，但是神奇地错了，大家可以帮忙证明一下为什么错了，反正我是找不出来。

if(t1-h1+1 <= 0 && t2 > 0){
  while(t2 > 0) q1[++t1] = s1[t2--];
}

贰：数理证明 & 时间复杂度

引理1 队列不保证单调性

证：

假设队列中有元素(表示距离) ：

$w_1<w_2<w_3, \cdot \cdot \cdot <w_n$

此时有新节点，距离设为 $v$

$v < w_1<w_2<w_3, \cdot \cdot \cdot <w_n$

依据Step2，栈之后有 （出栈的顺序）:

$w_1，w_2 ,w_3, \cdot \cdot \cdot ,w_n$

此时进行 $n-1$ 次松弛，队列有:

$v+a_1 < v+a_2 < \cdot \cdot \cdot <v+a_{n-1}$

假设 $w_n < v+a_1 （1）$

当 $v+a_n < v+a_1$ 时，

根据Step2后，此时栈中有 （出栈的顺序）：

$v + a_1, v + a_2, \cdot \cdot \cdot ,w_1,w_2,\cdot \cdot \cdot ,w_n$

假设之后并没有发生松弛操作，队列元素顺序将是：

$v + a_1, v + a_2, \cdot \cdot \cdot ,w_1,w_2,\cdot \cdot \cdot ,w_n$

那么根据 （1）式 ，此时队列没有单调性。

定理1 最多存在 $n$ 轮松弛

解释：因为队列没有单调性，所以它相当于朴素的SPFA，所以与SPFA一样存在$n$轮松弛。

最坏时间复杂度

设入队时间复杂度为 $\alpha$，根据 Step2，还摊价值为$\frac{1}{\alpha}$

因为最坏一共有 $n$ 轮松弛，所以循环次数为 $O(mn)$

所以，最坏时间复杂度为

$O(1 \cdot \frac{1}{\alpha} \cdot m \cdot n) = O(mn)$

叁：闲话

说实话，我想到了很多，但是没有实现，因为能力的有限，时间的限制。

我很痛苦，我亲手证明了我的优化的最坏时间复杂度为 $O(mn)$ ，尽管它对于一些稠密图以及精心设计的图跑得很快，但是改变不了什么。大家可以帮忙想想怎么优化。

SPFA也许这就这个命吧。