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

信奥赛C提高组csp-s之Dijkstra算法堆优化版邻接表Dijkstra堆优化版进阶版题目描述给定一个n nn个点m mm条有向边的带非负权图请你计算从s ss出发到每个点的距离。数据保证你能从s ss出发到任意点。输入格式第一行为三个正整数n , m , s n, m, sn,m,s。第二行起m mm行每行三个非负整数u i , v i , w i u_i, v_i, w_iui​,vi​,wi​表示从u i u_iui​到v i v_ivi​有一条权值为w i w_iwi​的有向边。输出格式输出一行n nn个空格分隔的非负整数表示s ss到每个点的距离。输入样例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 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤1051 ≤ m ≤ 2 × 10 5 1 \leq m \leq 2\times 10^51≤m≤2×105s 1 s 1s11 ≤ u i , v i ≤ n 1 \leq u_i, v_i\leq n1≤ui​,vi​≤n0 ≤ w i ≤ 10 9 0 \leq w_i \leq 10 ^ 90≤wi​≤109,0 ≤ ∑ w i ≤ 10 9 0 \leq \sum w_i \leq 10 ^ 90≤∑wi​≤109。题目分析节点数n≤105 ^55边数m≤2×105 ^55基础Dijkstra复杂度O(n²)会超时需要使用堆优化将复杂度降为O((nm)log n)堆优化思路使用优先队列小根堆存储节点和距离每次从堆顶取出距离最小的节点避免重复入队使用dist数组判断代码实现#includebits/stdc.husingnamespacestd;constlonglongINF1e18;// 足够大的无穷大值constintMAXN100005;intn,m,s;structEdge{intto;// 目标节点intweight;// 边权重};structNode{intid;// 节点编号longlongdist;// 起点到该节点的当前最短距离// 重载运算符用于优先队列小根堆booloperator(constNodeother)const{returndistother.dist;// 注意优先队列默认大根堆需要反向比较}};vectorEdgegraph[MAXN];longlongdist[MAXN];boolvisited[MAXN];// 用于记录节点是否已确定最短路径voiddijkstra_heap(intstart){// 初始化for(inti1;in;i){dist[i]INF;visited[i]false;}dist[start]0;// 创建优先队列小根堆priority_queueNodepq;pq.push({start,0});while(!pq.empty()){// 取出堆顶元素当前距离最小的节点Node currentpq.top();pq.pop();intucurrent.id;// 如果该节点已经处理过跳过if(visited[u])continue;// 标记节点u已确定最短路径visited[u]true;// 遍历u的所有邻接边for(constEdgeedge:graph[u]){intvedge.to;intwedge.weight;// 松弛操作if(dist[u]wdist[v]){dist[v]dist[u]w;// 将更新后的节点加入优先队列pq.push({v,dist[v]});}}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinnms;// 读取边信息构建邻接表for(inti0;im;i){intu,v,w;cinuvw;graph[u].push_back({v,w});}// 执行堆优化Dijkstra算法dijkstra_heap(s);// 输出结果for(inti1;in;i){coutdist[i] ;}coutendl;return0;}Dijkstra算法总结核心特点贪心策略每次选择当前已知最短路径的节点进行扩展适用范围仅适用于边权值为非负的图时间复杂度基础版O(n²)适合稠密图堆优化版O((nm)log n)适合稀疏图算法对比版本时间复杂度空间复杂度适用场景基础版O(n²)O(nm)节点较少或稠密图堆优化版O((nm)log n)O(nm)节点较多或稀疏图注意事项不能处理负权边Dijkstra算法基于贪心策略当存在负权边时贪心选择可能不再正确堆优化实现细节优先队列需要自定义比较函数同一个节点可能多次入队需要判断是否已处理使用visited数组避免重复处理更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html配套视频课信奥赛C提高组csp-s知识详解https://edu.csdn.net/course/detail/41081各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}