📷 题解插图【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)
在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 P3371「【模板】单源最短路径(弱化版)」给出了**非负权有向图单源最短路径(Single-Source Shortest Path, SSSP)**的标准数学模型,精准对标 CCF GESP 七级核心考点(图论基础、邻接表构建、Dijkstra 堆优化最短路)以及 CSP-S 初级图论建模。题目的核心计算瓶颈在于:面对多达 个节点与 条有向边(且存在重边与自环),若采用无权图的普通 BFS 无法处理权值差异,若采用朴素 Bellman-Ford 算法的 轮询松弛,运算量高达 ,将遭遇严重的超时评测(TLE)。破局的关键,在于利用边权非负()的结构性质,运用 Dijkstra 贪心松弛策略结合优先队列(小根堆):每次从未确定的候选节点中提取当前距源点最近的顶点,其最短距离在出堆瞬间即获得数学单调性锁定(后续任何经过其他未访问节点的路径由于权值非负,累加后绝不可能比当前值更优)。借助 std::priority_queue 维护动态距离,将顶点提取与出边松弛的总时间复杂度收敛至 ,在毫秒级内轻取海量边集,并兼顾不可达点输出 的大数边界。题目洛谷官方难度评级为普及/提高-。
luogu-P3371 【模板】单源最短路径(弱化版)
🔗 洛谷原题传送门:luogu-P3371 【模板】单源最短路径(弱化版)
题目描述
如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 ,分别表示点的个数、有向边的个数、出发点的编号。
接下来 行每行包含三个整数 ,表示一条 的,长度为 的边。
输出格式
输出一行 个整数,第 个表示 到第 个点的最短路径,若不能到达则输出 。
样例 #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提示
【数据范围】
对于 的数据:,;
对于 的数据:,;
对于 的数据:,;
对于 的数据:,,,,,保证数据随机。
Update 2022/07/29:两个点之间可能有多条边,敬请注意。
对于真正 的数据,请移步 P4779。请注意,该题与本题数据范围略有不同。
样例说明:

图片1到3和1到4的文字位置调换
题目深度剖析
1. 单源最短路径(SSSP)模型与图论表征
单源最短路径问题定义为:给定带权有向图 ,边权函数为 ,以及一个指定的源点 。我们需要计算从 到图中每一个顶点 的最小路径权重和 。
在存储结构上:
- 图中节点规模 ,边数 。
- 若采用邻接矩阵
int g[MAXN][MAXN],空间开销为 ,直接超出题目 的空间上限,且无法自然存储两点间的重边。 - 因此,必须采用**邻接表(
std::vector<Edge> adj[MAXN])**或链式前向星进行存图。邻接表空间复杂度为 ,仅需约 ,且遍历某个顶点的所有邻接出边效率极高。
2. Dijkstra 算法的核心贪心性质与数学证明
Dijkstra 算法是一种基于贪心策略(Greedy Approach)与广度优先搜索思想相结合的单源最短路算法。
集合划分与算法不变量: 算法维护两个不相交的顶点集合:
- 已确定最短路的顶点集合 (代码中由
visited[u] = true标识); - 尚未确定最短路的顶点集合 。
对于任意顶点 ,算法维护从源点 出发、且中间节点全部属于 的当前最短估计距离 。
贪心选择: 在每一步迭代中,算法从未确定集合 中挑选出 最小的顶点 : 将 加入集合 (标记已访问),随后利用 的所有出边 对其相邻节点 进行松弛(Relaxation):
正确性证明(反证法):
- 为什么在边权非负()的前提下,当前 最小的节点 可以立即确定最短路?
- 假设从 到 存在一条更短的真实路径 ,且 上至少经过了某个尚未加入集合 的节点 。
- 设路径 上从 出发离开集合 的第一个未访问节点为 。那么从 到 的距离必然满足: 因为在当前候选集中 具有最小距离,即 。
- 又因为图的所有边权非负(),从 继续走到 的后续路程长度必非负,所以:
- 这与“路径 比当前 更短”产生直接矛盾!
- 因此,在非负权图中,当前距离最小的顶点 的最短路径已然确定,贪心策略具备完备的数学正确性。
3. 优先队列(小根堆)优化与稀疏图工程落地
朴素 Dijkstra 算法每次通过线性扫描整个未访问集合寻找距离最小点,每轮需要 ,执行 轮总计 。当 时, 次运算,在 1.00s 内非常危险,更无法推广至大规模图。
借助 C++ STL 中的**优先队列(std::priority_queue)**构建小根堆:
- 堆元素存储
pair<int, int>,分别代表(当前距离, 顶点编号)。 - 提取当前最小距离顶点操作优化至 ;
- 每次成功松弛出边时,将更新后的
(dist[v], v)压入小根堆,总共最多插入 个元素; - 遇到堆中出队的冗余历史状态(即
visited[u] == true时)直接跳过(Lazy Deletion 懒惰删除)。 - 整体算法的时间复杂度被优雅地压缩至 。
4. 复杂度剖析与评测指标
- 时间复杂度:
- 堆中最多插入 个元素,每次插入或弹出耗时 。
- 每个顶点至多被作为合法节点访问一次,遍历其所有出边累计为 。
- 算法整体时间复杂度严格为 。
- 对于 ,运算步数约为 次,在现代 CPU 上执行耗时仅需 ,远低于 的时间限制。
- 空间复杂度:
- 邻接表
adj存储 条有向边,占用空间 ; - 距离数组
dist与访问标记visited占用空间 ; - 优先队列中最多同时容纳 个元素;
- 总空间复杂度为 ,内存峰值不超过 ,完全符合 的评测上限。
- 邻接表
样例逐步手推演算
以题目样例为例: 个顶点, 条边,源点 。 有向边集:,,,,,。
初始状态:,。小根堆压入 。
| 步骤 | 堆顶出队 | 顶点锁定状态 | 松弛邻接出边 | 松弛结果与堆操作 | 各点当前距离 |
|---|---|---|---|---|---|
| 初始 | - | 无 | - | 堆: | |
| 1 | , , | , 堆入 , 堆入 , 堆入 |
|||
| 2 | , | , 堆入 , 堆入 |
|||
| 3 | 无出边 | 无松弛 | |||
| 4 | 边 : , 不松弛 | ||||
| 5 | 历史冗余() | - | 直接跳过 | ||
| 6 | 历史冗余() | - | 直接跳过 |
最终堆空退出,各顶点最短距离为:,与样例输出完全吻合。
易错点与边界防坑指南
- 【防坑 1】重边、自环与优先队列中的冗余节点
题目在 2022 年官方更新明确指出:“两个点之间可能有多条边”。在使用堆优化 Dijkstra 时,同一个顶点可能因为被多次成功松弛而多次被推入优先队列。当该顶点第一次作为堆顶出队时,其全局最短路径已经确定,并被标记为
visited[u] = true。后续该顶点的旧记录再次出队时,必须第一时间使用if (visited[u]) continue;予以跳过。若遗漏此行剪枝,算法退化为指数级或者导致重复遍历出边而发生 TLE。 - 【防坑 2】不可达节点的输出与加法溢出防护
题目明确要求:“若不能到达则输出 ”。。
初始时将所有节点的距离初始化为
INF = 2147483647。在进行松弛判断时:if (dist[u] + w < dist[v])若 且 ,两者相加会导致 32 位有符号整型溢出产生未定义行为(变负数),从而引发严重的逻辑错误!因此必须在运算时强制转换为long long判断:if ((long long)dist[u] + w < dist[v])。 - 【防坑 3】优先队列小根堆的语法声明
C++ 中的
std::priority_queue默认是大根堆(std::less<T>,先出队最大值)。在求最短路时需要小根堆(先出队最小值),完整语法必须显式声明底层容器和比较仿函数:priority_queue<PII, vector<PII>, greater<PII>> pq;若遗漏后两个模板参数,堆将按大根堆排序,彻底破坏贪心选择单调性,得出完全错误的答案。 - 【防坑 4】静态内存分配与 C++11 规范
顶点数 ,邻接表数组
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;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务
生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Crit...
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3366 【模板】最小生成树
在通信基站管网布线、电力网架设以及交通枢纽规划等重大工程中,如何在保证所有节点相互连通的前提下,使铺设线路的总建设开销(边权之和)达到全局最小,是经典的最小生成树(Minimum Spanning Tree, MST)离散优化问题。洛谷 P3366「【模板】最小生成树」...
【GESP/CSP练习】GESP八级 / CSP-S 题解:luogu-P3388 【模板】割点(割顶)
在网络拓扑与通信基础设施分析中,评估图的联通健壮性与识别单点故障(Single Point of Failure, SPOF)是核心课题。对于给定的无向图 G = (V, E),若移去某顶点 u 及其关联的所有边后,图的连通分量数严格增加,则称顶点 u 为图的一个割点(...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

