信奥赛C++提高组csp-s之Dijkstra算法（朴素版）

信奥赛C++提高组csp-s之Dijkstra算法（朴素版）

邻接表+Dijkstra求解最短路（基础版）

题目描述

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

输入格式

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

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

输出格式

输出一行n nn个整数，第i ii个表示s ss到第i ii个点的最短路径，若不能到达则输出2 31 − 1 2^{31}-1231−1。

输入样例

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

说明/提示

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

两个点之间可能有多条边，敬请注意。

题目分析：

• 求从起点s到每个点的最短距离
• 如果无法到达则输出2 31 − 1 2^{31}-1231−1
• 节点数n ≤ 10 4 ，边数 m ≤ 5 × 10 5 n≤10^4，边数m≤5×10^5n≤104，边数m≤5×105
• 适合使用邻接表存储，基础Dijkstra可过

代码实现：

#include<bits/stdc++.h>usingnamespacestd;constlonglongINF=(1LL<<31)-1;// 2^31-1constintMAXN=10005;intn,m,s;structEdge{intto;// 目标节点intweight;// 边权重};// 邻接表存储图vector<Edge>graph[MAXN];// 存储起点到各点的最短距离longlongdist[MAXN];// 标记节点是否已确定最短路径boolvisited[MAXN];voiddijkstra(intstart){// 初始化for(inti=1;i<=n;i++){dist[i]=INF;visited[i]=false;}dist[start]=0;// 循环n次，每次确定一个节点的最短路径for(inti=1;i<=n;i++){// 步骤1：从未确定节点中找到距离起点最近的节点intu=-1;longlongminDist=INF;for(intj=1;j<=n;j++){if(!visited[j]&&dist[j]<minDist){minDist=dist[j];u=j;}}// 标记节点u已确定最短路径visited[u]=true;// 步骤2：松弛操作，更新u的邻居节点的距离for(constEdge&edge:graph[u]){intv=edge.to;intw=edge.weight;// 如果通过u到v的距离更短，则更新if(!visited[v]&&dist[u]+w<dist[v]){dist[v]=dist[u]+w;}}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m>>s;// 读取边信息，构建邻接表for(inti=1;i<=m;i++){intu,v,w;cin>>u>>v>>w;graph[u].push_back({v,w});}// 执行Dijkstra算法dijkstra(s);// 输出结果for(inti=1;i<=n;i++){cout<<dist[i]<<" ";}cout<<endl;return0;}

更多系列知识，请查看专栏：《信奥赛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>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

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>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}