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

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

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

OJ: luogu

题目 ID: P4779

难度:普及+/提高-

标签:Dijkstra最短路heapqpython

日期: 2026-07-17 03:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

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

思路

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

Python 知识

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

代码

python
import 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:])

原有 C++ 版本仍保留：

cpp
#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。