信奥赛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≤51 ≤ m ≤ 15 1\le m \le 151≤m≤15对于40 % 40\%40%的数据1 ≤ n ≤ 100 1\le n \le 1001≤n≤1001 ≤ m ≤ 10 4 1\le m \le 10^41≤m≤104对于70 % 70\%70%的数据1 ≤ n ≤ 1000 1\le n \le 10001≤n≤10001 ≤ 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≤1041 ≤ m ≤ 5 × 10 5 1\le m \le 5\times 10^51≤m≤5×1051 ≤ u , v ≤ n 1\le u,v\le n1≤u,v≤nw ≥ 0 w\ge 0w≥0∑ w 2 31 \sum w 2^{31}∑w231保证数据随机。两个点之间可能有多条边敬请注意。题目分析求从起点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可过代码实现#includebits/stdc.husingnamespacestd;constlonglongINF(1LL31)-1;// 2^31-1constintMAXN10005;intn,m,s;structEdge{intto;// 目标节点intweight;// 边权重};// 邻接表存储图vectorEdgegraph[MAXN];// 存储起点到各点的最短距离longlongdist[MAXN];// 标记节点是否已确定最短路径boolvisited[MAXN];voiddijkstra(intstart){// 初始化for(inti1;in;i){dist[i]INF;visited[i]false;}dist[start]0;// 循环n次每次确定一个节点的最短路径for(inti1;in;i){// 步骤1从未确定节点中找到距离起点最近的节点intu-1;longlongminDistINF;for(intj1;jn;j){if(!visited[j]dist[j]minDist){minDistdist[j];uj;}}// 标记节点u已确定最短路径visited[u]true;// 步骤2松弛操作更新u的邻居节点的距离for(constEdgeedge:graph[u]){intvedge.to;intwedge.weight;// 如果通过u到v的距离更短则更新if(!visited[v]dist[u]wdist[v]){dist[v]dist[u]w;}}}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnms;// 读取边信息构建邻接表for(inti1;im;i){intu,v,w;cinuvw;graph[u].push_back({v,w});}// 执行Dijkstra算法dijkstra(s);// 输出结果for(inti1;in;i){coutdist[i] ;}coutendl;return0;}更多系列知识请查看专栏《信奥赛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;}