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

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

0 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

Tip

b站讲解

📌 题目分析

给定数据： * \(N = 10^5\)（点数），\(M = 2 \times 10^5\)（边数）。 * 边权非负，有向图。 * 目标：求单源最短路径（从 \(s\) 到所有点的距离）。

👉 本质： 在带权图中寻找最短路径。题目背景提到的“\(100 \to 60\)”暗示了 SPFA 算法在构造数据下会退化为 \(O(NM)\)，导致超时。对于本题的规模，必须使用更稳定的算法。

👉 类型： Dijkstra 算法（堆优化版）。

---

🧠 解题思路

1️⃣ 为什么选择 Dijkstra 而非 SPFA？

• SPFA： 虽然平均时间复杂度不错，但在特殊构造的网格图或“菊花图”中会退化。题目背景正是提醒大家，标准版最短路要用 Dijkstra。
• Dijkstra： 核心是贪心思想。只要边权为非负，一旦某个点被确定为当前距离最近且已处理，它的最短路就固定了。
• 优化： 朴素 Dijkstra 复杂度为 \(O(N^2)\)。配合 优先队列（堆），可以将复杂度优化至 \(O(M \log N)\)，完美通过 \(10^5\) 级别的数据。

2️⃣ 算法核心步骤（松弛操作）

1. 初始化：源点距离 dist[s] = 0，其余点 dist[i] = INF。
2. 将源点放入优先队列。
3. 不断从队列取出当前 dist 最小的点 \(u\)：
   • 如果 \(u\) 已访问过（确定了最短路），跳过。
   • 遍历 \(u\) 的所有出边 \((u, v, w)\)：
     • 如果 dist[u] + w < dist[v]（这就是松弛），更新 dist[v] 并将 \((dist[v], v)\) 压入队列。

3️⃣ 存储结构：链式前向星或邻接表

由于 \(N, M\) 较大，不能使用邻接矩阵。建议使用 std::vector<Edge> adj[N] 或 链式前向星 存储。

---

💻 C++代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;
const int MAXN = 100005; // 顶点数可以开到 10万级了！

// 邻接表存图：adj[u] 里面存的是从 u 出发的所有边。
// pair<int, int> 的含义是：{相邻节点 v, 边权 w}
vector<pair<int, int>> adj[MAXN]; 

int dis[MAXN];
int vis[MAXN];
int n, m, s; // n个点, m条边, 起点为s

void dijkstra_heap(int s) {
    // 初始化
    for(int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = 0;
    }
    dis[s] = 0;

    // 定义一个小根堆（优先队列）
    // 队列里存的 pair<int, int> 含义是：{当前距离, 节点编号}
    // 注意：一定要把距离放在 pair 的第一个位置，因为 C++ 的 pair 默认按照第一个元素进行排序！
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 把起点推入堆中
    pq.push({0, s});

    while(!pq.empty()) {
        // 1. 直接拿出堆顶元素（距离起点最近的点）
        int u = pq.top().second;
        pq.pop();

        // 2. 如果这个点之前已经被拿出来更新过周围的点，就跳过（重要！）
        // 这是因为同一个点可能会带着不同的距离被多次推入堆中，我们只认第一次（最短的那次）
        if(vis[u]) continue;
        vis[u] = 1; // 标记为已处理

        // 3. 遍历这个点 u 的所有真正相邻的点
        for(auto edge : adj[u]) {
            int v = edge.first;     // 相邻点 v
            int weight = edge.second; // 边权 w

            // 4. 松弛操作（更新最短路）
            if(dis[u] + weight < dis[v]) {
                dis[v] = dis[u] + weight;
                // 如果发现了更短的路径，就把新的距离和点推入堆中
                pq.push({dis[v], v}); 
            }
        }
    }
}

int main() {
    // 优化输入输出速度（可选）
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> s;

    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 构建邻接表（这里以有向图为例，如果是无向图还需要加一句 adj[v].push_back({u, w});）
        adj[u].push_back({v, w}); 
    }

    dijkstra_heap(s);

    for(int i = 1; i <= n; i++) {
        if (dis[i] == INF) {
            cout << "INF ";
        } else {
            cout << dis[i] << " ";
        }
    }

    return 0;
}

---

⚠️ 易错点

1. 优先队列的排序： priority_queue 默认是大顶堆。为了取最小值，需要自定义比较函数（如上文代码中的 greater）或者存入距离的负值。
2. vis 数组的作用： Dijkstra 中，每个点出队并标记 vis 后，它的最短路就已经确定。不加 vis 判断会导致大量冗余松弛，效率退化。
3. INF 值的选择： 边权和可能很大（本题 \(\sum w_i\) 可达 \(10^9\)），dist 数组建议使用 long long，且 INF 设置要足够大（如 1e18 或 0x3f3f3f3f3f3f3f3f）。
4. 图的性质： Dijkstra 不适用于带负权边的图。如果有负权边，请使用 Bellman-Ford 或 SPFA（并祈祷数据不卡它）。

---

🚀 一句话总结

Dijkstra 堆优化：贪心选最近，松弛更相邻；$O(M \log N)$ 稳如狗，边权非负是前提。

---

🔥 补充：Dijkstra vs SPFA

• Dijkstra： 稳定，像“涟漪”一样向外扩散，点一旦变蓝（vis）就不再回头。
• SPFA： 不稳定，像“消息传播”，点可以多次入队。虽然能处理负权边，但在正式比赛中，如果确定无负权，请永远优先选择优先队列优化的 Dijkstra，避免 Ag 变 Cu。