P3371 单源最短路径(弱化版)

P3371 单源最短路径(弱化版)

在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 P3371「【模板】单源最短路径(弱化版)」给出了**非负权有向图单源最短路径(Single-Source Shortest Path, SSSP)**的标准数学模型,精准对标 CCF GESP 七级核心考点(图论基础、邻接表构建、Dijkstra 堆优化最短路)以及 CSP-S 初级图论建模。题目的核心计算瓶颈在于:面对多达 n=104n = 10^4 个节点与 m=5×105m = 5 \times 10^5 条有向边(且存在重边与自环),若采用无权图的普通 BFS 无法处理权值差异,若采用朴素 Bellman-Ford 算法的 O(nm)O(nm) 轮询松弛,运算量高达 5×1095 \times 10^9,将遭遇严重的超时评测(TLE)。破局的关键,在于利用边权非负(w≥0w \ge 0)的结构性质,运用 Dijkstra 贪心松弛策略结合优先队列(小根堆):每次从未确定的候选节点中提取当前距源点最近的顶点,其最短距离在出堆瞬间即获得数学单调性锁定(后续任何经过其他未访问节点的路径由于权值非负,累加后绝不可能比当前值更优)。借助 std::priority_queue 维护动态距离,将顶点提取与出边松弛的总时间复杂度收敛至 O((n+m)log⁡n)O((n+m) \log n),在毫秒级内轻取海量边集,并兼顾不可达点输出 231−12^{31}-1 的大数边界。题目洛谷官方难度评级为普及/提高-。

luogu-P3371 【模板】单源最短路径(弱化版)

🔗 洛谷原题传送门:luogu-P3371 【模板】单源最短路径(弱化版)

题目描述

如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,sn,m,s,分别表示点的个数、有向边的个数、出发点的编号。

接下来 mm 行每行包含三个整数 u,v,wu,v,w,表示一条 u→vu \to v 的,长度为 ww 的边。

输出格式

输出一行 nn 个整数,第 ii 个表示 ss 到第 ii 个点的最短路径,若不能到达则输出 231−12^{31}-1。

样例 #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

提示

【数据范围】
对于 20%20\% 的数据:1≤n≤51\le n \le 5,1≤m≤151\le m \le 15;
对于 40%40\% 的数据:1≤n≤1001\le n \le 100,1≤m≤1041\le m \le 10^4;
对于 70%70\% 的数据:1≤n≤10001\le n \le 1000,1≤m≤1051\le m \le 10^5;
对于 100%100\% 的数据:1≤n≤1041 \le n \le 10^4,1≤m≤5×1051\le m \le 5\times 10^5,1≤u,v≤n1\le u,v\le n,w≥0w\ge 0,∑w<231\sum w< 2^{31},保证数据随机。

Update 2022/07/29:两个点之间可能有多条边,敬请注意。

对于真正 100%100\% 的数据,请移步 P4779。请注意,该题与本题数据范围略有不同。

样例说明:

图片1到3和1到4的文字位置调换


题目深度剖析

1. 单源最短路径(SSSP)模型与图论表征

单源最短路径问题定义为:给定带权有向图 G=(V,E)G = (V, E),边权函数为 w:E→R≥0w: E \to \mathbb{R}_{\ge 0},以及一个指定的源点 s∈Vs \in V。我们需要计算从 ss 到图中每一个顶点 v∈Vv \in V 的最小路径权重和 dist(s,v)\text{dist}(s, v)。

在存储结构上:

  • 图中节点规模 n≤104n \le 10^4,边数 m≤5×105m \le 5 \times 10^5。
  • 若采用邻接矩阵 int g[MAXN][MAXN],空间开销为 10000×10000×4 B≈400 MB10000 \times 10000 \times 4 \text{ B} \approx 400 \text{ MB},直接超出题目 125 MB125 \text{ MB} 的空间上限,且无法自然存储两点间的重边。
  • 因此,必须采用**邻接表(std::vector<Edge> adj[MAXN])**或链式前向星进行存图。邻接表空间复杂度为 O(n+m)O(n + m),仅需约 10 MB10 \text{ MB},且遍历某个顶点的所有邻接出边效率极高。

2. Dijkstra 算法的核心贪心性质与数学证明

Dijkstra 算法是一种基于贪心策略(Greedy Approach)与广度优先搜索思想相结合的单源最短路算法。

集合划分与算法不变量: 算法维护两个不相交的顶点集合:

  1. 已确定最短路的顶点集合 SS(代码中由 visited[u] = true 标识);
  2. 尚未确定最短路的顶点集合 V∖SV \setminus S。

对于任意顶点 v∈Vv \in V,算法维护从源点 ss 出发、且中间节点全部属于 SS 的当前最短估计距离 dist[v]dist[v]。

贪心选择: 在每一步迭代中,算法从未确定集合 V∖SV \setminus S 中挑选出 dist[u]dist[u] 最小的顶点 uu:

u=arg⁡min⁡v∈V∖Sdist[v]u = \arg\min_{v \in V \setminus S} dist[v]

将 uu 加入集合 SS(标记已访问),随后利用 uu 的所有出边 (u,v)(u, v) 对其相邻节点 vv 进行松弛(Relaxation):

dist[v]=min⁡(dist[v],dist[u]+w(u,v))dist[v] = \min(dist[v], dist[u] + w(u, v))

正确性证明(反证法):

  • 为什么在边权非负(w≥0w \ge 0)的前提下,当前 dist[u]dist[u] 最小的节点 uu 可以立即确定最短路?
  • 假设从 ss 到 uu 存在一条更短的真实路径 PP,且 PP 上至少经过了某个尚未加入集合 SS 的节点 x∈V∖Sx \in V \setminus S。
  • 设路径 PP 上从 ss 出发离开集合 SS 的第一个未访问节点为 xx。那么从 ss 到 xx 的距离必然满足: dist(s,x)≥dist[x]\text{dist}(s, x) \ge dist[x] 因为在当前候选集中 uu 具有最小距离,即 dist[u]≤dist[x]dist[u] \le dist[x]。
  • 又因为图的所有边权非负(w≥0w \ge 0),从 xx 继续走到 uu 的后续路程长度必非负,所以: length(P)≥dist(s,x)≥dist[x]≥dist[u]\text{length}(P) \ge \text{dist}(s, x) \ge dist[x] \ge dist[u]
  • 这与“路径 PP 比当前 dist[u]dist[u] 更短”产生直接矛盾!
  • 因此,在非负权图中,当前距离最小的顶点 uu 的最短路径已然确定,贪心策略具备完备的数学正确性。

3. 优先队列(小根堆)优化与稀疏图工程落地

朴素 Dijkstra 算法每次通过线性扫描整个未访问集合寻找距离最小点,每轮需要 O(n)O(n),执行 nn 轮总计 O(n2)O(n^2)。当 n=104n = 10^4 时,n2=108n^2 = 10^8 次运算,在 1.00s 内非常危险,更无法推广至大规模图。

借助 C++ STL 中的**优先队列(std::priority_queue)**构建小根堆:

  • 堆元素存储 pair<int, int>,分别代表 (当前距离, 顶点编号)。
  • 提取当前最小距离顶点操作优化至 O(log⁡n)O(\log n);
  • 每次成功松弛出边时,将更新后的 (dist[v], v) 压入小根堆,总共最多插入 mm 个元素;
  • 遇到堆中出队的冗余历史状态(即 visited[u] == true 时)直接跳过(Lazy Deletion 懒惰删除)。
  • 整体算法的时间复杂度被优雅地压缩至 O((n+m)log⁡n)O((n + m) \log n)。

4. 复杂度剖析与评测指标

  • 时间复杂度:
    • 堆中最多插入 O(m)O(m) 个元素,每次插入或弹出耗时 O(log⁡n)O(\log n)。
    • 每个顶点至多被作为合法节点访问一次,遍历其所有出边累计为 O(m)O(m)。
    • 算法整体时间复杂度严格为 O((n+m)log⁡n)O((n + m) \log n)。
    • 对于 n=104,m=5×105n = 10^4, m = 5 \times 10^5,运算步数约为 5×105×14≈7×1065 \times 10^5 \times 14 \approx 7 \times 10^6 次,在现代 CPU 上执行耗时仅需 0.1∼0.2 s0.1 \sim 0.2 \text{ s},远低于 1.00 s1.00 \text{ s} 的时间限制。
  • 空间复杂度:
    • 邻接表 adj 存储 mm 条有向边,占用空间 O(m)O(m);
    • 距离数组 dist 与访问标记 visited 占用空间 O(n)O(n);
    • 优先队列中最多同时容纳 O(m)O(m) 个元素;
    • 总空间复杂度为 O(n+m)O(n + m),内存峰值不超过 20 MB20 \text{ MB},完全符合 125.00 MB125.00 \text{ MB} 的评测上限。

样例逐步手推演算

以题目样例为例:n=4n = 4 个顶点,m=6m = 6 条边,源点 s=1s = 1。 有向边集:(1→2,2)(1 \to 2, 2),(2→3,2)(2 \to 3, 2),(2→4,1)(2 \to 4, 1),(1→3,5)(1 \to 3, 5),(3→4,3)(3 \to 4, 3),(1→4,4)(1 \to 4, 4)。

初始状态:dist[1]=0dist[1] = 0,dist[2]=dist[3]=dist[4]=INFdist[2] = dist[3] = dist[4] = \text{INF}。小根堆压入 (0,1)(0, 1)。

步骤堆顶出队 (d,u)(d, u)顶点锁定状态松弛邻接出边 (u→v,w)(u \to v, w)松弛结果与堆操作各点当前距离 dist[1..4]dist[1..4]
初始-无-堆:{(0,1)}\{(0, 1)\}[0,∞,∞,∞][0, \infty, \infty, \infty]
1(0,1)(0, 1)visited[1]=truevisited[1] = \text{true}1→2(2)1 \to 2 (2), 1→3(5)1 \to 3 (5), 1→4(4)1 \to 4 (4)dist[2]←2dist[2] \gets 2, 堆入 (2,2)(2, 2)dist[3]←5dist[3] \gets 5, 堆入 (5,3)(5, 3)dist[4]←4dist[4] \gets 4, 堆入 (4,4)(4, 4)[0,2,5,4][0, 2, 5, 4]
2(2,2)(2, 2)visited[2]=truevisited[2] = \text{true}2→3(2)2 \to 3 (2), 2→4(1)2 \to 4 (1)dist[3]←min⁡(5,2+2)=4dist[3] \gets \min(5, 2+2) = 4, 堆入 (4,3)(4, 3)dist[4]←min⁡(4,2+1)=3dist[4] \gets \min(4, 2+1) = 3, 堆入 (3,4)(3, 4)[0,2,4,3][0, 2, 4, 3]
3(3,4)(3, 4)visited[4]=truevisited[4] = \text{true}无出边无松弛[0,2,4,3][0, 2, 4, 3]
4(4,3)(4, 3)visited[3]=truevisited[3] = \text{true}3→4(3)3 \to 4 (3)边 3→43 \to 4: dist[3]+3=7>dist[4]=3dist[3] + 3 = 7 > dist[4] = 3, 不松弛[0,2,4,3][0, 2, 4, 3]
5(4,4)(4, 4)历史冗余(visited[4]==truevisited[4] == \text{true})-直接跳过[0,2,4,3][0, 2, 4, 3]
6(5,3)(5, 3)历史冗余(visited[3]==truevisited[3] == \text{true})-直接跳过[0,2,4,3][0, 2, 4, 3]

最终堆空退出,各顶点最短距离为:dist=[0,2,4,3]dist = [0, 2, 4, 3],与样例输出完全吻合。


易错点与边界防坑指南

  1. 【防坑 1】重边、自环与优先队列中的冗余节点 题目在 2022 年官方更新明确指出:“两个点之间可能有多条边”。在使用堆优化 Dijkstra 时,同一个顶点可能因为被多次成功松弛而多次被推入优先队列。当该顶点第一次作为堆顶出队时,其全局最短路径已经确定,并被标记为 visited[u] = true。后续该顶点的旧记录再次出队时,必须第一时间使用 if (visited[u]) continue; 予以跳过。若遗漏此行剪枝,算法退化为指数级或者导致重复遍历出边而发生 TLE。
  2. 【防坑 2】不可达节点的输出与加法溢出防护 题目明确要求:“若不能到达则输出 231−12^{31}-1”。231−1=21474836472^{31}-1 = 2147483647。 初始时将所有节点的距离初始化为 INF = 2147483647。在进行松弛判断时: if (dist[u] + w < dist[v]) 若 dist[u]=2147483647dist[u] = 2147483647 且 w>0w > 0,两者相加会导致 32 位有符号整型溢出产生未定义行为(变负数),从而引发严重的逻辑错误!因此必须在运算时强制转换为 long long 判断:if ((long long)dist[u] + w < dist[v])。
  3. 【防坑 3】优先队列小根堆的语法声明 C++ 中的 std::priority_queue 默认是大根堆(std::less<T>,先出队最大值)。在求最短路时需要小根堆(先出队最小值),完整语法必须显式声明底层容器和比较仿函数: priority_queue<PII, vector<PII>, greater<PII>> pq; 若遗漏后两个模板参数,堆将按大根堆排序,彻底破坏贪心选择单调性,得出完全错误的答案。
  4. 【防坑 4】静态内存分配与 C++11 规范 顶点数 n≤10000n \le 10000,邻接表数组 vector<Edge> adj[MAXN] 以及标记数组 dist[MAXN]、visited[MAXN] 必须定义在全局静态存储区(BSS 段)。严禁在 main() 函数内部开辟大数组或使用变长数组(VLA),防止触发 Linux 系统栈溢出(Segmentation Fault / RE)。

C++ 完整参考实现

/**
 * 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)
 * 题号: P3371
 * 归属: GESP七级 / CSP-S / 洛谷经典图论模板
 * 博客: https://www.coderli.com/gesp-7-luogu-p3371/
 * 标准: C++11 (严格遵循 CCF GESP 官方规范)
 */

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

using namespace std;

// 题目定义:若不能到达则输出 2^31 - 1
const int INF = 2147483647;

// 最大顶点数量常数,题目给定 n <= 10000
const int MAXN = 10005;

// 有向边结构体
struct Edge {
    int to;     // 目标顶点编号
    int weight; // 边权
};

// 邻接表:adj[u] 存储从顶点 u 出发的所有有向边
vector<Edge> adj[MAXN];

// dist[i] 记录从出发点 s 到顶点 i 的当前最短距离
int dist[MAXN];

// visited[i] 标记顶点 i 的最短路径是否已被最终锁定并出队
bool visited[MAXN];

// 优先队列堆元素定义:pair<当前距离, 顶点编号>
// C++ 的 pair 默认先按 first 比较,若 first 相等再按 second 比较
typedef pair<int, int> PII;

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    // 读入 m 条有向边并构建邻接表
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    // 初始化所有顶点到源点的距离为无穷大 INF (2^31 - 1)
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
        visited[i] = false;
    }

    // 起点到自身的距离初始化为 0
    dist[s] = 0;

    // 定义小根堆优先队列:距离较小的顶点优先出队
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, s});

    // Dijkstra 核心贪心松弛循环
    while (!pq.empty()) {
        PII cur = pq.top();
        pq.pop();

        int u = cur.second;

        // 若当前顶点已被锁定处理过,跳过冗余的历史入堆记录
        if (visited[u]) {
            continue;
        }
        visited[u] = true;

        // 遍历从当前顶点 u 出发的所有出边进行松弛
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            int w = adj[u][i].weight;

            // 防溢出松弛判断:若经由 u 前往 v 的路径更短
            // 采用 (long long) 防止 dist[u] + w 超过 32 位整型上限
            if (!visited[v] && (long long)dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // 按题意要求输出从 s 出发到达 1..n 各顶点的最短距离,不能到达输出 2^31 - 1
    for (int i = 1; i <= n; ++i) {
        cout << dist[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于