【模板】单源最短路径（标准版）

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

用 heapq 实现带过期状态判断的 Dijkstra，求非负权有向图单源最短路。

OJ: luogu

题目 ID: P4779

难度:普及+/提高-

标签:Dijkstra最短路heapqpython

创建: 2026-07-17 03:00

更新: 2026-10-16T00:00:00.000Z

后置题目

相似题目

luogu P3371【模板】单源最短路径（弱化版）同一单源最短路模型，非负权改用堆优化 Dijkstra 的标准做法

题意

求非负权有向图中起点到每个节点的最短距离。

思路

Dijkstra 每次从堆中取当前距离最小的状态，尝试松弛所有出边。堆中可能保留旧状态，若弹出的距离不等于数组中的最新距离就跳过。

Python 知识

heapq 是最小堆，元组按距离优先比较。
current != distance[node] 是无 decrease-key 堆的标准过期判断。
print(*distance[1:]) 直接输出一行结果。

代码

标准写法：

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
25import sys
from heapq import heappop, heappush


input = sys.stdin.buffer.readline
n, edges, start = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for _ in range(edges):
    u, v, weight = map(int, input().split())
    graph[u].append((v, weight))

infinity = 10**30
distance = [infinity] * (n + 1)
distance[start] = 0
heap = [(0, start)]
while heap:
    current, node = heappop(heap)
    if current != distance[node]:
        continue
    for neighbor, weight in graph[node]:
        candidate = current + weight
        if candidate < distance[neighbor]:
            distance[neighbor] = candidate
            heappush(heap, (candidate, neighbor))
print(*distance[1:])

零基础逐行注释版（main-user.py），适合第一次用 heapq 写 Dijkstra 时对照阅读：

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
48
49
50
51import sys
from heapq import heappop, heappush

# 边用 (终点 v, 边权 w) 表示
type Edge = tuple[int, int]
# 邻接表：g[u] 是出边列表，Graph 的每个元素本身也是列表
type Graph = list[list[Edge]]


def dijkstra(g: Graph, src: int) -> list[int]:
    infinity = 10**30
    # dis[v] 表示当前已知的 src 到 v 的最短距离，先全部设为无穷
    dis = [infinity for i in range(len(g))]
    dis[src] = 0

    # 小根堆，存放 (距离, 节点)。距离写在前面，元组比较时优先比距离
    heap = [(0, src)]

    while heap:
        disu, u = heappop(heap)
        # 堆里可能有同一个节点的多条旧记录，若弹出距离比 dis[u] 大说明已过期
        if disu > dis[u]:
            continue
        # 用 u 去松弛它的所有出边
        for v, w in g[u]:
            disv = disu + w
            # 只有能让 v 变短才更新，并把新状态压入堆
            if disv < dis[v]:
                dis[v] = disv
                heappush(heap, (disv, v))
    return dis


def solve(data):
    # 依次读出 n 个点、m 条边、起点 s
    n, m, s = next(data), next(data), next(data)
    # 邻接表用 1..n 编号，所以开 n+1 个位置
    g: list[list[Edge]] = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        g[u].append((v, w))

    return dijkstra(g, s)


if __name__ == "__main__":
    # 一次读完输入，切成整数迭代器，比逐行 readline 更快
    data = iter(map(int, sys.stdin.buffer.read().split()))
    dis = solve(data)
    # 起点编号从 1 开始，跳过 dis[0]；不可达的点仍为 infinity
    print(*dis[1:])

该版本用 type Edge = tuple[int, int]、type Graph = list[list[Edge]] 声明类型别名，阅读时可以直接看出邻接表是「点 → 出边列表」的两层结构，因此 g[u] 本身是列表、for v, w in g[u] 取出的才是边。注意 type 语句需要 Python 3.12 及以上；在旧版本上把它写成 Edge = tuple[int, int] 赋值形式即可。

原有 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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;
const long long INF = (1LL << 62);

int n, m, s;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;
long long weight_edge[MAXM];
long long dist_arr[MAXN]; // dist_arr[u] 表示从源点 s 到 u 的当前最短路
bool done[MAXN];

struct Node {
    long long dist;
    int u;
    bool operator<(const Node &other) const {
        return dist > other.dist;
    }
};

void add_edge(int u, int v, long long w) {
    edge_cnt++;
    to[edge_cnt] = v;
    weight_edge[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        dist_arr[i] = INF;
        done[i] = false;
    }

    priority_queue<Node> q;
    dist_arr[s] = 0;
    q.push({0, s});

    while (!q.empty()) {
        Node cur = q.top();
        q.pop();
        int u = cur.u;
        if (done[u]) {
            continue;
        }
        done[u] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            long long w = weight_edge[i];
            if (dist_arr[v] > dist_arr[u] + w) {
                dist_arr[v] = dist_arr[u] + w;
                q.push({dist_arr[v], v});
            }
        }
    }
}

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

    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    dijkstra();

    for (int i = 1; i <= n; i++) {
        if (i > 1) {
            cout << ' ';
        }
        cout << dist_arr[i];
    }
    cout << '\n';
    return 0;
}

复杂度

时间 O((n+m)log n)，空间 O(n+m)。

总结

非负边权优先使用堆优化 Dijkstra。

P4779 【模板】单源最短路径（标准版）

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60$ ；

$\text{Ag} \rightarrow \text{Cu}$ ；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 $n$ 个点， $m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$ 。第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$ ，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

输入输出样例 #1

输入 #1

text

输出 #1

text

10 2 4 3

说明/提示

样例解释请参考数据随机的模板题。

$1 \leq n \leq 10^5$ ；

$1 \leq m \leq 2\times 10^5$ ；

$s = 1$ ；

$1 \leq u_i, v_i\leq n$ ；

$0 \leq w_i \leq 10 ^ 9$ ,

$0 \leq \sum w_i \leq 10 ^ 9$ 。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

【模板】单源最短路径（标准版）

目录

题意

思路

Python 知识

代码

复杂度

总结