本文章将同步分享于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也许这就这个命吧。