最短路(Spfa)

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

边权全正的无向图单源最短路模板：堆优化 Dijkstra 按距离从小到大定型每个点，惰性删除过期堆条目，N 第一次出堆即得答案，复杂度 O(M log M)。

OJ: roj

题目 ID: 1382

难度:普及+/提高-

标签:图论最短路Dijkstra堆python

创建: 2026-09-30 07:57

更新: 2026-10-07 11:01

后置题目

形式化题目

给定 $N$ 个点、 $M$ 条边的带权无向图（ $N \leqslant 100000$ ， $M \leqslant 500000$ ），每条边权 $c_i$ 是不超过 $1000$ 的正整数。图中可能有重边和自环，数据保证 $1$ 与 $N$ 连通。求点 $1$ 到点 $N$ 的最短路径长度，只输出距离值。

样例是一张 4 个点 4 条边的图，加粗的两条边构成最优路线 $1 \to 2 \to 4$ ：

flowchart LR
  s1["1"] ---|"1"| s2["2"]
  s2 ---|"1"| s3["3"]
  s3 ---|"1"| s4["4"]
  s2 ---|"1"| s4
  linkStyle 0,3 stroke:#c0392b,stroke-width:3px

观察这张图： $2$ 到 $4$ 之间既有长度 $1$ 的直接边，也有绕经 $3$ 、总长 $2$ 的路线。最短路要求把一个点对之间所有可能路线放在一起比较总长，而不是只盯住某条边或某条路——这正是最短路算法要替我们做的全局比较。

正解

思路

从朴素做法出发。 最短路的原始定义是松弛操作：若经过 $u$ 能把到 $v$ 的距离改得更小，就更新

\mathrm{dist}[v] = \min\bigl(\mathrm{dist}[v],\ \mathrm{dist}[u] + w(u,v)\bigr).

从 $\mathrm{dist}[1] = 0$ 、其余为 $\infty$ 出发，反复扫描全部边做松弛直到不再变化，就是 Bellman-Ford 算法，复杂度 $O(NM)$ 。本题 $N \leqslant 10^5$ 、 $M \leqslant 5\times10^5$ ， $NM$ 高达 $5\times10^{10}$ ，连时限的百分之一都跑不完。

瓶颈在哪。 每一轮都无差别扫描所有边，而绝大多数边在当时根本不可能引起有效松弛。改进方向自然有两种：要么"只扫刚变小的点"，要么"给该轮到谁定序"。

路线一：把被松弛成功的点塞进队列，下一轮只从它们出发扩展，这就是 SPFA（本题官方标题与标程的做法）。平均很快，但最坏复杂度仍是 $O(NM)$ ，没有任何保证，Python 实现常数又大。
路线二：本题边权全为正，这个条件允许更强的贪心——当前候选距离最小的未定型点，它的距离已经不可能再被别的路改小，可以一次性"定型"。用小根堆维护"谁的候选距离最小"，就是堆优化 Dijkstra，复杂度 $O(M\log M)$ ，有硬保证。

"第一次弹出堆即定型"为什么对？归纳来看：所有边权为正，任何还没定型的点若想把 $u$ 改得更小，路径必须先经过某个距离不小于 $d$ 的点再走正权边，只会更大。所以弹出 $(d, u)$ 时 $d$ 就是 $u$ 的最终最短距离。

用样例走一遍流程（点按编号 $1..4$ ）：

步骤	弹出 $(d, u)$	动作	$\mathrm{dist}$ 状态 $[1,2,3,4]$
初始	—	$\mathrm{dist}[1]=0$ 入堆	$[0, \infty, \infty, \infty]$
1	$(0, 1)$	松弛 $1\to2$ ： $0+1<\infty$	$[0, 1, \infty, \infty]$
2	$(1, 2)$	松弛 $2\to3$ 、 $2\to4$ 均成功	$[0, 1, 2, 2]$
3	$(2, 3)$	松弛 $3\to4$ ： $2+1=3 > 2$ ，失败	$[0, 1, 2, 2]$
4	$(2, 4)$	$u=N$ ，直接返回 2	答案 $2$

表格里有两个值得注意的细节：第 3 步经过 $3$ 绕路到 $4$ 反而更贵，松弛自动淘汰了它；第 4 步 $4$ 被弹出时答案就已确定，不用等堆空——"命中终点提前返回"是完全安全的。

实现上的三个要点。

惰性删除：一个点每被松弛成功一次就压一次堆，堆里会同时存在同一点的多个条目。弹出时若 $d > \mathrm{dist}[u]$ ，说明这是过期条目，直接跳过。这比手写"可删除堆"简单得多，也是 Python 里最省事的标准写法。
重边与自环不用特判：无向边在两端各存一条即可；自环因 $c > 0$ 永远满足 $\mathrm{dist}[u]+c > \mathrm{dist}[u]$ ，松弛条件"严格小于"让它自动失效；重边中较大的一条会在比较中自然落败。
读入规模： $M = 5\times10^5$ 时输入约 7.8MB，必须 sys.stdin.buffer.read() 一次读完再按空白切分，逐行 input() 会先死在读入上。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47#!/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-09-30 08:00
# update_at: 2026-09-30 08:00

import sys
from heapq import heappop, heappush

INF = 1 << 60  # 距离哨兵：大于任何可能的最短路（最长不超过 n*w ≤ 1e5 * 1000）


def dijkstra(n: int, adj: list[list[tuple[int, int]]]) -> int:
    """返回 1 到 n 的最短距离：权值全为正，堆优化 Dijkstra 按距离从小到大敲定每个点。"""
    dist = [INF] * (n + 1)
    dist[1] = 0
    heap = [(0, 1)]  # (候选距离, 点)：堆顶是当前候选距离最小的点
    while heap:
        d, u = heappop(heap)
        if u == n:  # n 第一次出堆时它的候选距离已不可能再变小
            return d
        if d > dist[u]:  # 过期条目：u 后来又被更小的距离松弛过，跳过
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(heap, (nd, v))
    return dist[n]  # 题面保证 1 到 n 连通，正常运行到不了这里


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b, c = next(data), next(data), next(data)  # 无向边 a—b，长 c
        adj[a].append((b, c))
        adj[b].append((a, c))  # 重边、自环照常存，松弛时自然被淘汰

    print(dijkstra(n, adj))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84/**
 * 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-05 00:11
 * update_at: 2026-10-05 00:11
 */

// 1382 最短路：边权全为正的无向图单源最短路，堆优化 Dijkstra。
// N 第一次出堆时它的候选距离已不可能再变小，直接得到答案。

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

const int MAXN = 100005;
const int MAXM = 500005;

typedef long long ll;

int n, m;
int head[MAXN], nxt[MAXM * 2], to[MAXM * 2], edge_cnt; // 链式前向星，无向边存两条
ll weight[MAXM * 2]; // 边权用 ll，最短路累加不会溢出
ll dist_[MAXN]; // dist_[u] 表示当前 1 到 u 的候选最短距离
bool done[MAXN]; // done[u] 为 true 表示 u 已定型（第一次出堆）

priority_queue< pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> > > heap; // 小根堆：(候选距离, 点)

// 加一条 u -> v、长 w 的边。
void add_edge(int u, int v, int w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 堆优化 Dijkstra：按距离从小到大定型每个点，返回 1 到 n 的最短距离。
// 重边、自环不用特判：松弛条件是严格小于，较大的重边自然落败，正权自环永远松弛失败。
ll dijkstra() {
    const ll INF = 1e18;
    for (int i = 1; i <= n; i++) {
        dist_[i] = INF;
        done[i] = false;
    }
    dist_[1] = 0;
    while (!heap.empty()) heap.pop(); // 清空全局堆
    heap.push(make_pair(0LL, 1));

    while (!heap.empty()) {
        int u = heap.top().second;
        ll d = heap.top().first;
        heap.pop();
        if (done[u]) continue; // 过期条目：u 已被更小的距离定型过，跳过
        done[u] = true;
        if (u == n) return d; // n 第一次出堆，答案已确定，提前返回
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            ll nd = d + weight[i];
            if (nd < dist_[v]) { // 松弛成功才压堆，堆中可能同点多条目，靠 done 惰性删除
                dist_[v] = nd;
                heap.push(make_pair(nd, v));
            }
        }
    }
    return dist_[n]; // 题面保证 1 与 n 连通，正常运行到不了这里
}

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

    cin >> n >> m;
    edge_cnt = 0;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add_edge(a, b, c); // 无向边两端各存一条
        add_edge(b, a, c);
    }

    cout << dijkstra() << "\n";

    return 0;
}

复杂度

时间复杂度：每次松弛成功压一次堆，无向边两个方向的松弛总次数不超过 $2M$ ，堆操作 $O(\log M)$ ，总计 $O\bigl((N+M)\log M\bigr)$ ，与 C++ 标准堆优化最短路解法同阶。实测最大数据（ $N=10^5$ ， $M=5\times10^5$ ）本地运行约 0.45s。
空间复杂度：邻接表 $O(M)$ 、dist 与堆 $O(N+M)$ ，合计 $O(N+M)$ 。Python 对象开销大，实测峰值约 238MB，会超出本题 128MB 内存限制；这是 Python 解法的已知代价（C++ 同算法约 20MB），需要严格卡内存时应换 C++ 或改用扁平数组存边。

总结

本题是单源最路模板：边权全正 ⟹ 堆优化 Dijkstra 成立；只求 $1\to N$ 的距离值 ⟹ $N$ 第一次出堆即可返回。
推导主线：Bellman-Ford 的 $O(NM)$ 全量扫描是瓶颈 ⟹ SPFA"只扫刚变小的点"（官方标程路线，最坏无保证）⟹ Dijkstra"按距离从小到大定型" $O(M\log M)$ （本文采用的路线，复杂度有硬保证）。
三个实现要点可以直接迁移到任何最短路题：惰性删除过期堆条目、重边自环不特判（严格小于的松弛条件兜底）、大数据一次 read() 再切分。

【题目描述】

给定 $M$ 条边， $N$ 个点的带权无向图。求 $1 $到 $N$ 的最短路。

【输入】

第一行： $N,M(N≤100000，M≤500000)$ ；

接下来 $M$ 行 $3$ 个正整数： $a\_i,b\_i,c\_i 表示a\_i,b\_i之间有一条长度为c\_i的路，c\_i≤1000$ 。

【输出】

一个整数，表示 $1$ 到 $N$ 的最短距离。

【输入样例】

text

【输出样例】

text

【提示】

【样例解释】

注意图中可能有重边和自环,数据保证 $1$ 到 $N$ 有路径相连。

【来源】

一本通在线评测

最短路(Spfa)

目录

形式化题目

正解

思路

代码

复杂度

总结