带负权边的有向图求 1 到 n 最短路:SPFA 只把距离刚被改小的点入队做松弛,队列空即最优;距离必须开 64 位,答案可达 -2e13。
OJ: roj
题目 ID: 1419
难度:普及+/提高-
标签:图论最短路SPFABellman-Ford一本通python
创建: 2026-10-07 15:45
更新: 2026-10-07 15:45
形式化题目
给定一张有向图
要求
即所有从
因为不含负环,绕圈只会让权值变大或不变,最小值一定在某条简单路径上取到,
所以"路径"按"可以重复经过点"理解也不会改变答案。样例
题面称"有向连通图",但算法只依赖"点
正解
思路
先确认算法。 本题边权可以是负数,Dijkstra 依赖的"当前距离最小的点已经定稿、 不会再被改写"不再成立(一条负边随时可能把它的距离继续压小),所以只能用允许负权的 Bellman–Ford 或它的队列优化版本 SPFA——题目的名字就是后者。
朴素做法与瓶颈。 Bellman–Ford 把全部
关键观察。 一条边
,其余点为 ,把点 入队; - 反复取出队首
,对它的每条出边 :若 , 就更新 ;并且如果 此刻不在队列里,把 入队; - 队列为空时结束,
就是答案。
为什么这样是对的、又一定会停? 两点夹逼:
每次被写入的值都对应一条真实的 路径 (初值 除外),所以 永远不小于真正的最短距离 ; - 队列空时不存在还能松弛的边,即对每条边都有
。 把这条不等式沿着最短路 逐边相加, 得到 。
两者合起来就是
四个必须处理的细节。
| 细节 | 处理方式 | 不处理的后果 |
|---|---|---|
| 距离类型 | dist 用 64 位整数(C++ 的 ll;Python 整数天然无上限) |
最负路径可达 |
无穷大 INF |
取 |
INF 太小会被真实距离改写,可达点被误判 |
| 重边与自环 | 都照常加进图里,不判重、不跳过 | 重边只是多条候选路径,松弛取小天然处理; |
| 入队标记 | inq[u] 记录 |
同一个点同一时刻被重复入队,队列膨胀、白费时间(不影响答案) |
第三点在样例里就出现了:边
下面对样例(
| 步骤 | 出队 |
dist[1] |
dist[2] |
队列 | 发生了什么 |
|---|---|---|---|---|---|
| 初始 | — | 0 | |||
| 1 | 1 | 0 | 边 |
||
| 2 | 2 | 0 | 自环 |
答案
SPFA 到底省掉了什么? 看真实数据第 7 点:
两个常数级优化。 一是 SLF(Small Label First):队列用双端队列,
新点入队时如果它的估计距离比当前队首还小,就插到队首优先处理,
实测能明显减少出队次数。二是出边顺序:C++ 头插建图,点 main.py 读入后做一次 edges.reverse() 就是为了让两版的出边顺序
一致、便于逐条对照。顺序会实质影响松弛次数——真实数据第 10 点按 HDU 4889 构造,
只有
代码
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++ 版(同一算法):
/**
* 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 同阶,为
次松弛; 实际远小于它——只有距离被改小的点才入队,总量是 量级, 为每个点的平均出队次数(本组数据里第 7 点 ,最坏的第 9 点 )。 C++ 实测最慢的第 9 点 0.06 s(限时 1000 ms),Python 最慢的第 9 点约 0.89 s。 - 空间:C++ 的链式前向星按
条有向边存 to / nxt / wt, 加上head / dist / inq,总计,实测峰值 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 只把距离刚被改小的点放进队列;队列空意味着所有边都松弛不动了,
此时
恰好满足最短路的最优性条件,这就是正确性的全部内容。 long long是本题唯一容易丢分的地方:的链上每条边权 , 答案 ,远超 32 位范围。 把 dist换成int重跑,第 5、6、7、9 四个点会当场算错(第 7 点输出), 这是很好的自检手段。 - 别被"负权"误导以为答案一定为负:真实数据第 8 点的答案就是正的
, 最短路只是所有候选路径里最小的那一条。 - SLF 与出边顺序只改常数、不改答案:它们决定的是同一个点被出队几次, 本题第 10 点就是专门用来放大这个差异的构造点。
- 题面保证无负环,所以不需要"入队次数超过
就报负环"的判定; 真要做负环判定,给每个点加一个入队计数器即可,主循环一行都不用改。