信奥赛C++提高组csp-s之Dijkstra算法（堆优化版）-171主机测评

信奥赛C++提高组csp-s之Dijkstra算法（堆优化版）

在这里插入图片描述

邻接表+Dijkstra堆优化版（进阶版）

题目描述

给定一个

$n$ 个点，

$m$ 条有向边的带非负权图，请你计算从

$s$ 出发，到每个点的距离。

数据保证你能从

$s$ 出发到任意点。

输入格式

第一行为三个正整数

n, m, s

$n, m, s$ 。第二行起

$m$ 行，每行三个非负整数

u_i, v_i, w_i

$u_{i}, v_{i}, w_{i}$ ，表示从

u_i

$u_{i}$ 到

v_i

$v_{i}$ 有一条权值为

w_i

$w_{i}$ 的有向边。

输出格式

输出一行

$n$ 个空格分隔的非负整数，表示

$s$ 到每个点的距离。

输入样例

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

输出样例

0 2 4 3

说明/提示

≤

1 \\leq n \\leq 10^5

$1 \leq n \leq 1 0^{5}$ ；

≤

1 \\leq m \\leq 2\\times 10^5

$1 \leq m \leq 2 \times 1 0^{5}$ ；

s = 1

$s = 1$ ；

≤

1 \\leq u_i, v_i\\leq n

$1 \leq u_{i}, v_{i} \leq n$ ；

≤

0 \\leq w_i \\leq 10 ^ 9

$0 \leq w_{i} \leq 1 0^{9}$ ,

≤

∑

≤

0 \\leq \\sum w_i \\leq 10 ^ 9

$0 \leq \sum w_{i} \leq 1 0^{9}$ 。

题目分析：

节点数n≤10 $^5 5，边数m≤2×10 5 ^5 5$
基础Dijkstra复杂度O(n²)会超时
需要使用堆优化将复杂度降为O((n+m)log n)

堆优化思路：

使用优先队列（小根堆）存储节点和距离
每次从堆顶取出距离最小的节点
避免重复入队，使用dist数组判断

代码实现：

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18; // 足够大的无穷大值
const int MAXN = 100005;

int n, m, s;
struct Edge {
int to; // 目标节点
int weight; // 边权重
};

struct Node {
int id; // 节点编号
long long dist; // 起点到该节点的当前最短距离

// 重载<运算符，用于优先队列（小根堆）
bool operator<(const Node& other) const {
return dist > other.dist; // 注意：优先队列默认大根堆，需要反向比较
}
};

vector<Edge> graph[MAXN];
long long dist[MAXN];
bool visited[MAXN]; // 用于记录节点是否已确定最短路径

void dijkstra_heap(int start) {
// 初始化
for (int i = 1; i <= n; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[start] = 0;

// 创建优先队列（小根堆）
priority_queue<Node> pq;
pq.push({start, 0});

while (!pq.empty()) {
// 取出堆顶元素（当前距离最小的节点）
Node current = pq.top();
pq.pop();
int u = current.id;

// 如果该节点已经处理过，跳过
if (visited[u]) continue;

// 标记节点u已确定最短路径
visited[u] = true;

// 遍历u的所有邻接边
for (const Edge& edge : graph[u]) {
int v = edge.to;
int w = edge.weight;

// 松弛操作
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
// 将更新后的节点加入优先队列
pq.push({v, dist[v]});
}
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> m >> s;

// 读取边信息，构建邻接表
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
}

// 执行堆优化Dijkstra算法
dijkstra_heap(s);

// 输出结果
for (int i = 1; i <= n; i++) {
cout << dist[i] << " ";
}
cout << endl;

return 0;
}

Dijkstra算法总结

核心特点：

贪心策略：每次选择当前已知最短路径的节点进行扩展

适用范围：仅适用于边权值为非负的图

时间复杂度：

基础版：O(n²)，适合稠密图
堆优化版：O((n+m)log n)，适合稀疏图

算法对比：

版本时间复杂度空间复杂度适用场景

基础版	O(n²)	O(n+m)	节点较少或稠密图
堆优化版	O((n+m)log n)	O(n+m)	节点较多或稀疏图

注意事项：

不能处理负权边：Dijkstra算法基于贪心策略，当存在负权边时，贪心选择可能不再正确

堆优化实现细节：

优先队列需要自定义比较函数
同一个节点可能多次入队，需要判断是否已处理
使用visited数组避免重复处理

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html

配套视频课信奥赛C++提高组csp-s知识详解： https://edu.csdn.net/course/detail/41081

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

在这里插入图片描述

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

在这里插入图片描述

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

在这里插入图片描述 GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}

信奥赛C++提高组csp-s之Dijkstra算法（堆优化版）