SPFA(II)

GitHub跳转原题关系图返回列表

带负权边的有向图求 1 到 n 最短路:SPFA 只把距离刚被改小的点入队做松弛,队列空即最优;距离必须开 64 位,答案可达 -2e13。

OJ: roj

题目 ID: 1419

难度:普及+/提高-

标签:图论最短路SPFABellman-Ford一本通python

创建: 2026-10-07 15:45

更新: 2026-10-07 15:45

形式化题目

给定一张有向图 G=(V,E)G = (V, E),∣V∣=n|V| = n、∣E∣=m|E| = m,每条边写成三元组 (s,t,d)(s, t, d), 表示一条从 ss 指向 tt、长度为 dd 的有向边,其中 1⩽s,t⩽n1 \leqslant s, t \leqslant n、 −109⩽d⩽109-10^9 \leqslant d \leqslant 10^9。边允许重复出现(重边),也允许两端相同(自环)。 图保证不含负环(任意有向环的边权之和都 ⩾0\geqslant 0),并且点 11 可以到达点 nn。

要求

min⁡P: 1⇝n∑e∈Pde,\min_{P:\, 1 \rightsquigarrow n} \sum_{e \in P} d_e ,

即所有从 11 走到 nn 的路径中边权总和的最小值,输出这个整数。

因为不含负环,绕圈只会让权值变大或不变,最小值一定在某条简单路径上取到, 所以"路径"按"可以重复经过点"理解也不会改变答案。样例 n=2n = 2、 边为 (1,2,1)(1,2,1)、(1,2,−1)(1,2,-1)、(2,2,0)(2,2,0) 时答案是 −1-1:走那条权为 −1-1 的重边即可, 自环 2→22 \to 2 权值为 00,走不走都一样。

题面称"有向连通图",但算法只依赖"点 11 可达点 nn"这一条;从 11 出发不可达的点 距离会一直保持 ∞\infty,不会影响答案。

正解

思路

先确认算法。 本题边权可以是负数,Dijkstra 依赖的"当前距离最小的点已经定稿、 不会再被改写"不再成立(一条负边随时可能把它的距离继续压小),所以只能用允许负权的 Bellman–Ford 或它的队列优化版本 SPFA——题目的名字就是后者。

朴素做法与瓶颈。 Bellman–Ford 把全部 mm 条边松弛 n−1n-1 轮:第 rr 轮之后 只保证"最多经过 rr 条边的最短路"已经算对,要 n−1n-1 轮才能收尾。 n=20000n = 20000、m=40000m = 40000 时上界是 (n−1)×m≈8×108(n-1) \times m \approx 8 \times 10^8 次松弛, 代价高且绝大多数是白做的:某一轮里被真正改小的点往往只有寥寥几个, 其余点的出边都在做"算一遍、发现不变"的无用功。

关键观察。 一条边 (u,v,d)(u, v, d) 只有在 dist[u]\mathrm{dist}[u] 刚刚被改小之后, 才可能算出更小的 dist[u]+d\mathrm{dist}[u] + d。于是不必按轮扫全边, 只维护一个队列保存"距离刚被改小、还没拿它的出边去松弛"的点:

  1. dist[1]=0\mathrm{dist}[1] = 0,其余点为 ∞\infty,把点 11 入队;
  2. 反复取出队首 uu,对它的每条出边 (u,v,d)(u, v, d):若 dist[u]+d<dist[v]\mathrm{dist}[u] + d < \mathrm{dist}[v], 就更新 dist[v]\mathrm{dist}[v];并且如果 vv 此刻不在队列里,把 vv 入队;
  3. 队列为空时结束,dist[n]\mathrm{dist}[n] 就是答案。

为什么这样是对的、又一定会停? 两点夹逼:

  • dist[v]\mathrm{dist}[v] 每次被写入的值都对应一条真实的 1⇝v1 \rightsquigarrow v 路径 (初值 ∞\infty 除外),所以 dist[v]\mathrm{dist}[v] 永远不小于真正的最短距离 δ(v)\delta(v);
  • 队列空时不存在还能松弛的边,即对每条边都有 dist[v]⩽dist[u]+d\mathrm{dist}[v] \leqslant \mathrm{dist}[u] + d。 把这条不等式沿着最短路 1=v0→v1→⋯→vk=n1 = v_0 \to v_1 \to \cdots \to v_k = n 逐边相加, 得到 dist[n]⩽δ(n)\mathrm{dist}[n] \leqslant \delta(n)。

两者合起来就是 dist[n]=δ(n)\mathrm{dist}[n] = \delta(n)。至于收敛:只要图中没有负环, 每个点的距离只会被改小有限次,队列必然变空;有负环时点会被无限次入队, 那时才需要"入队次数 >n−1> n-1 即判定负环"的额外计数——本题题面已排除负环, 这段不用写。

四个必须处理的细节。

细节 处理方式 不处理的后果
距离类型 dist 用 64 位整数(C++ 的 ll;Python 整数天然无上限) 最负路径可达 −(n−1)×109≈−2×1013-(n-1) \times 10^9 \approx -2 \times 10^{13},32 位装不下
无穷大 INF 取 4×10184 \times 10^{18},比 −2×1013-2 \times 10^{13} 大若干个数量级 INF 太小会被真实距离改写,可达点被误判
重边与自环 都照常加进图里,不判重、不跳过 重边只是多条候选路径,松弛取小天然处理;d⩾0d \geqslant 0 的自环不等式恒不成立(d<0d < 0 的自环就是负环,题面已排除)
入队标记 inq[u] 记录 uu 当前是否在队列里 同一个点同一时刻被重复入队,队列膨胀、白费时间(不影响答案)

第三点在样例里就出现了:边 (2,2,0)(2,2,0) 松弛时算出 dist[2]+0=dist[2]\mathrm{dist}[2] + 0 = \mathrm{dist}[2], 不满足严格小于,天然被挡掉。第二点是本题真正的卡点,下面用真实数据说明。

下面对样例(n=2n = 2,边 (1,2,1)(1,2,1)、(1,2,−1)(1,2,-1)、(2,2,0)(2,2,0))逐轮追踪。 C++ 用链式前向星头插建图,点 11 的出边顺序是输入顺序的逆序,先试 −1-1 再试 11:

步骤 出队 uu dist[1] dist[2] 队列 发生了什么
初始 — 0 ∞\infty [1][1] dist[1]=0\mathrm{dist}[1] = 0,点 1 入队
1 1 0 −1-1 [2][2] 边 1→21 \to 2(−1-1):−1<∞-1 < \infty,更新并让点 2 入队;边 1→21 \to 2(11)算出 11,不小于 −1-1,跳过
2 2 0 −1-1 [][] 自环 2→22 \to 2(00)算出 −1-1,不小于 −1-1,跳过;队列空,结束

答案 −1-1。这张表把"重边不用特判"和"自环天然被过滤"两件事都演示完了: 重边就是两条彼此独立的候选,先到的那条占优;自环的松弛不等式恒不成立。

SPFA 到底省掉了什么? 看真实数据第 7 点:n=20000n = 20000 的一条链, 每条边权都是 −109-10^9,于是 dist[i]=−(i−1)×109\mathrm{dist}[i] = -(i-1) \times 10^9。 Bellman–Ford 的轮数上界是 n−1=19999n - 1 = 19999 轮、每轮扫 19999 条边, 而 SPFA 在这里每个点只出队一次,总共 20000 次出队、19999 次松弛。 省掉的正是"距离这一轮根本没变的点"的那部分工作。

两个常数级优化。 一是 SLF(Small Label First):队列用双端队列, 新点入队时如果它的估计距离比当前队首还小,就插到队首优先处理, 实测能明显减少出队次数。二是出边顺序:C++ 头插建图,点 uu 的出边顺序 是输入顺序的逆序,main.py 读入后做一次 edges.reverse() 就是为了让两版的出边顺序 一致、便于逐条对照。顺序会实质影响松弛次数——真实数据第 10 点按 HDU 4889 构造, 只有 n=45n = 45、m=66m = 66,却能把松弛次数推到 1.26×107≈3⋅2221.26 \times 10^7 \approx 3 \cdot 2^{22}: 出边取输入顺序时 Python 要跑 4.5 s,取头插顺序(与 C++ 一致)时只要 298 次出队, C++ 两版都在 10 ms 以内。顺序只影响快慢,不影响答案。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:12
# update_at: 2026-10-07 15:45

import sys
from collections import deque

INF = 4 * 10**18  # 松弛起点:比最负路径 -(n-1)*1e9 ≈ -2e13 大若干数量级

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Graph = list[list[tuple[int, int]]]  # g[u] = 出边列表,每条边是 (终点 v, 边权 w)


def shortest(n: int, g: Graph) -> int:
    """SPFA:以 1 为源点做队列优化的 Bellman-Ford,回答“1 到 n 的最短距离”。"""
    dist = [INF] * (n + 1)  # dist[u]:1 到 u 的当前最短距离
    inq = bytearray(n + 1)  # inq[u] = 1 表示 u 正在队列里,避免同一时刻重复入队
    dist[1] = 0
    q = deque([1])
    inq[1] = 1
    push_back = q.append
    push_front = q.appendleft
    pop_front = q.popleft
    while q:
        u = pop_front()
        inq[u] = 0
        du = dist[u]
        head_dist = dist[q[0]] if q else INF  # 队首距离,SLF 小优化用
        for v, w in g[u]:
            nd = du + w
            if nd < dist[v]:  # 找到更短的路,v 需要重新入队
                dist[v] = nd
                if not inq[v]:
                    inq[v] = 1
                    if nd < head_dist:  # SLF:估计距离更小的点插到队首优先处理
                        push_front(v)
                        head_dist = nd
                    else:
                        push_back(v)
    return dist[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    g: Graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        s, t, d = next(data), next(data), next(data)
        g[s].append((t, d))
    for edges in g:
        edges.reverse()  # 头插建图,出边顺序与 C++ 链式前向星一致
    print(shortest(n, g))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:12
 * update_at: 2026-10-07 15:12
 */
// main.cpp:SPFA(队列优化的 Bellman-Ford)求 1 到 n 的最短路,允许负权边。
// 数据范围:N<=20000, M<=40000, -1e9<=D<=1e9,保证无负环且 1 可达 n。
// 答案最负约 -(n-1)*1e9 ≈ -2e13,必须用 long long,INF 也要远大于这个量级。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 20005; // 最大点数,多开几个防止越界
const int MAXM = 40005; // 最大边数
const ll INF = 4e18;    // 松弛起点:比最负路径 -2e13 大若干个数量级

// 链式前向星存图:适合边数上万、又要按点遍历出边的场景
int head[MAXN]; // head[u]:点 u 的第一条出边编号,0 表示没有出边
int nxt[MAXM];  // 同一起点的下一条出边编号
int to[MAXM];   // 边的终点
ll wt[MAXM];    // 边的权值
int edge_cnt;   // 已经加入的边数

ll dist[MAXN];  // dist[u]:从 1 到 u 的当前最短距离
bool inq[MAXN]; // inq[u]:点 u 是否正在队列里,防止同一时刻重复入队

int n, m;

// 加入一条 u -> v 的权值为 w 的有向边
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    to[edge_cnt] = v;
    wt[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// SPFA 求以 1 为源点的最短路;无负环时队列必然收敛
void spfa() {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        inq[i] = false;
    }
    deque<int> q; // 用双端队列,配合下面的 SLF 小优化
    dist[1] = 0;
    q.push_back(1);
    inq[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        inq[u] = false;
        // 只有 dist[u] 刚刚变小的点才可能松弛邻居,这正是 SPFA 比 Bellman-Ford 快的原因
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            ll nd = dist[u] + wt[e];
            if (nd < dist[v]) { // 找到更短的路,v 需要重新入队
                dist[v] = nd;
                if (!inq[v]) {
                    inq[v] = true;
                    // SLF:估计距离比队首还小的点优先处理,实测能减少入队次数
                    if (!q.empty() && dist[v] < dist[q.front()]) {
                        q.push_front(v);
                    } else {
                        q.push_back(v);
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int s, t;
        ll d;
        cin >> s >> t >> d;
        add_edge(s, t, d); // 重边与自环直接照常加入即可
    }

    spfa();

    cout << dist[n] << "\n"; // 题目保证 1 可达 n,dist[n] 不会是 INF
    return 0;
}

复杂度

  • 时间:最坏与 Bellman–Ford 同阶,为 O(NM)=8×108O(NM) = 8 \times 10^8 次松弛; 实际远小于它——只有距离被改小的点才入队,总量是 O(kM)O(kM) 量级, kk 为每个点的平均出队次数(本组数据里第 7 点 k=1k = 1,最坏的第 9 点 k≈181k \approx 181)。 C++ 实测最慢的第 9 点 0.06 s(限时 1000 ms),Python 最慢的第 9 点约 0.89 s。
  • 空间:C++ 的链式前向星按 MM 条有向边存 to / nxt / wt, 加上 head / dist / inq,总计 O(N+M)O(N + M),实测峰值 8.5 MB; Python 用 list[list[tuple[int, int]]] 存邻接表,实测峰值约 23 MB(限制 256 MB)。
  • 与 Python 解法的关系:main.py 是同一算法的 Python 版本, 结构一一对应:链式前向星换成邻接表、inq 用 bytearray、SLF 用 deque 两端插入。 时间上最慢的第 9 点约 0.89 s,离 1000 ms 只剩一成余量, 是本题 Python 侧唯一的风险点(见总结)。

总结

  • 边权有负数就必须放弃 Dijkstra:堆优化 Dijkstra 的"出堆即定稿"依赖非负边权, 一条负边就能推翻它。同一题面系列的 1420【Dijkastra(II)】正是边权非负的那一支, 两题图模型相同,算法不能互换。
  • SPFA 消除的瓶颈是"重复松弛没有变化的点":Bellman–Ford 每轮扫全边, SPFA 只把距离刚被改小的点放进队列;队列空意味着所有边都松弛不动了, 此时 dist\mathrm{dist} 恰好满足最短路的最优性条件,这就是正确性的全部内容。
  • long long 是本题唯一容易丢分的地方:n=20000n = 20000 的链上每条边权 −109-10^9, 答案 −19999000000000≈−2×1013-19999000000000 \approx -2 \times 10^{13},远超 32 位范围。 把 dist 换成 int 重跑,第 5、6、7、9 四个点会当场算错(第 7 点输出 −1632269824-1632269824), 这是很好的自检手段。
  • 别被"负权"误导以为答案一定为负:真实数据第 8 点的答案就是正的 268882251268882251, 最短路只是所有候选路径里最小的那一条。
  • SLF 与出边顺序只改常数、不改答案:它们决定的是同一个点被出队几次, 本题第 10 点就是专门用来放大这个差异的构造点。
  • 题面保证无负环,所以不需要"入队次数超过 n−1n-1 就报负环"的判定; 真要做负环判定,给每个点加一个入队计数器即可,主循环一行都不用改。