OneCoder Avatar
OneCodercoderli.com · 1023 篇博文
【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)📷 题解插图

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P3371 【模板】单源最短路径(弱化版)

📅 2026-10-03·✍️ OneCoder·计算中...·⏱️ 20 分钟

在交通网络寻径、物流供应链调度与通信路由协议中,求解从指定始发枢纽到网络中所有连通节点的最优开销,是离散优化与图论的核心基石。洛谷 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

Code7 行
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

样例输出 #1

Code1 行
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)与广度优先搜索思想相结合的单源最短路算法。

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

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

对于任意顶点 ,算法维护从源点 出发、且中间节点全部属于 的当前最短估计距离 。

贪心选择: 在每一步迭代中,算法从未确定集合 中挑选出 最小的顶点 : 将 加入集合 (标记已访问),随后利用 的所有出边 对其相邻节点 进行松弛(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. 【防坑 1】重边、自环与优先队列中的冗余节点 题目在 2022 年官方更新明确指出:“两个点之间可能有多条边”。在使用堆优化 Dijkstra 时,同一个顶点可能因为被多次成功松弛而多次被推入优先队列。当该顶点第一次作为堆顶出队时,其全局最短路径已经确定,并被标记为 visited[u] = true。后续该顶点的旧记录再次出队时,必须第一时间使用 if (visited[u]) continue; 予以跳过。若遗漏此行剪枝,算法退化为指数级或者导致重复遍历出边而发生 TLE。
  2. 【防坑 2】不可达节点的输出与加法溢出防护 题目明确要求:“若不能到达则输出 ”。。 初始时将所有节点的距离初始化为 INF = 2147483647。在进行松弛判断时: if (dist[u] + w < dist[v]) 若 且 ,两者相加会导致 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 规范 顶点数 ,邻接表数组 vector<Edge> adj[MAXN] 以及标记数组 dist[MAXN]、visited[MAXN] 必须定义在全局静态存储区(BSS 段)。严禁在 main() 函数内部开辟大数组或使用变长数组(VLA),防止触发 Linux 系统栈溢出(Segmentation Fault / RE)。

C++ 完整参考实现

C++98 行
/**
 * 题目: 【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;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!