SPFA（Shortest Path Faster Algorithm）是一个让人又爱又恨的存在。它写起来比 Dijkstra 简单，还能处理负权边，在随机图上运行速度极快。
然而，如果盲目使用 SPFA，可能会导致一串鲜红的 TLE。
为什么方格图天生“克” SPFA？
与其说 SPFA 是一个最短路径算法，不如说它是一个基于队列优化的迭代松弛工具。它的核心逻辑是：只要一个点 $u$ 的最短距离变小了，那么它所有出边的终点 $v$ 都有可能被进一步更新。
在 Dijkstra 算法中，贪心策略保证了每个节点出队时即为最优解（$dist$ 具有单调性）。而 SPFA 不具备单调性。 在方格图中，从起点到终点存在指数级数量的简单路径。如果通过控制边序或权重，使算法先沿着一条边数较多、初始权值较大的路径（长链）更新了大量后续节点，随后才扫描到一条总权值更小的“捷径”，SPFA 将不得不对所有受影响的后继节点进行重复松弛与重新入队。 出题人可以利用这一点，构造多达 $O(V)$ 层这种“捷径”。每发现一条新的捷径，SPFA 就要把后面的节点重新洗一遍。最终，每个节点入队的次数不再是常数 $k$，而是变成了线性 $O(V)$，导致总复杂度退化为 $O(V imes E)$，即 $O(V^2)$（在方格图中 $E ext{ 约等于 } 4V$）。
SPFA 的效率模型如下： $$W = \sum_{i=1}^{|V|} (count_i \times out\_degree_i)$$
变量定义：
- $W$：算法的总工作量（即松弛操作的总次数）。
- $|V|$：图中节点的总数。
- $count_i$：节点 $i$ 进入队列并被取出的总次数。
- $out\_degree_i$：节点 $i$ 的出度（即从该点出发的边数）。
总工作量 $W = \sum (count_i \times out\_degree_i)$。 在方格图中，$out\_degree \approx 4$，$count_i \approx V$。 则 $W \approx 4 \times V \times V = 4V^2$。
构造“捷径陷阱”
for(int i=0;i<R-1;i++){
for(int j=0;j<C;j++){
int cur=i*C+j;
int rit=cur+1;
int dow=cur+C;
int cro=dow+1;
adde(cur,rit,1);
adde(cur,dow,1);
adde(cur,cro,10);
}
}代码中定义了三种边： 水平边 (rit)：权值为 1。 垂直边 (dow)：权值为 1。 对角边 (cro)：权值为 10。
从 $(i, j)$ 到达其右下角邻居 $(i+1, j+1)$，走对角线只需要 1 步（代价 10），而走正交边（右+下）需要 2 步（代价 $1+1=2$）。
当 $C=N, R=M$ 时：二维灾难的叠加
在 SPFA 的 BFS 逻辑下，它会按队列的先后顺序处理节点。对角线虽然代价高（10），但它能在第一轮迭代中就触达 $(i+1, j+1)$。此时，SPFA 会带着这个错误的高代价（10）继续向右、向下扩散，污染后续大量的节点。 由于每一行、每一列都存在这种“先用对角线走捷径，后用正交边纠正”的情况，每一层级的更新都会触发下一层级的集体重洗。 入队的总次数会随着网格的面积呈现非线性爆发。理论上，每个节点可能被重新入队 $O(\sqrt{V})$ 到 $O(V)$ 次。 $$W \approx O((M \times N)^2)$$ 如果是一个 $500 \times 500$ 的图，节点数 25 万，平方级的操作量直接奔向百亿量级，必死无疑。
当 $C=N, R=2$ 时：细长长链的“全量背刺”
这种情况最为隐蔽且致命。由于只有两行，图变成了一条极其细长的带状结构。
当第一行第 i 个节点被纠正为更小的值时，它必须触发第二行第 i+1 个及之后所有节点的重新入队。 当第一行第 i+1 个节点被纠正时，又要再触发一遍。 在 $N$ 较小时，队列的处理速度尚能覆盖这种重复。 当 $N$ 足够大时，队列中堆积的“待修正”任务呈几何倍数增加。此时，正确的信息在队尾苦苦挣扎，而错误的信息已经跑到了终点。每一次微小的修正都会导致后面大量节点集体“反悔”重跑。 虽然只有两行，但它将 SPFA 退化成了最纯粹的 $O(N^2)$。在 $N=6000$ 时，$6000^2 = 3.6 \times 10^7$，考虑到每个点出队还要扫描 3 条边，常数因子放大后，轻松突破 1 秒的限时。
这段代码利用了 “短路（Steps）代价大，长路（Steps）代价小” 的悖论。在 $2 \times N$ 的长条图中，这种矛盾被拉到了极致，让 SPFA 在“不断纠错”的死循环中耗尽寿命。
那些“玄学优化”有用吗？
为了救活 SPFA，大佬们发明了很多优化手段，但在精心构造的方格图面前，大多是“缓刑”：
- SLF (Small Label First)：如果待入队节点的距离小于队首，就插到队头。 SLF 在面对诱导性极强的‘阶梯式’权值时，会导致队列频繁调整，反而增加常数开销。
- LLL (Large Label Last)：只有距离小于平均值的才出队。 计算平均值本身就有开销，面对强针对性数据时效果有限。
所以，不要试图用“玄学优化”去挑战出题人卡 SPFA 的决心。
总结
满足“步数短的路径权值大，步数长的路径权值小”，SPFA 就会在网格图中反复横跳。这样节点就会频繁入队，算法复杂度达到 $O(N^2)$。
私房话
“稳”要比“快那一点点”重要。
方格图是容易构造出极端数据的场景之一。当你在写 while(!q.empty()) 的时候，想想有没有可能是被卡住，如果是，请自觉右手转弯写 Dijkstra。