6
不是这玩意咋上榜的
woc两秒没看傍八了
第零篇？\HUGE{第零篇？}第零篇？
----------------------------------------------------第一篇----------------------------------------------------------
前言：
可能更好的学习体验？
> 本文适合深色模式食用
本帖分为三个部分，
1.算法讲解
2.代码解析
3.真题演练
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
作者的话：
额，被老师逼迫了，所以来写帖子 顺便水个精华帖 。我会写四篇帖子。三篇是单源最短路，一篇是全源最短路。这是第一篇迪杰斯特拉。我觉得只讲思路和代码，不讲例题就不是一篇好的精华帖，所以，这个帖子被分为了三个部分，算法讲解，代码分析和真题演练。作者还苦修了一国庆的markdowm排版，大家可以评价一下这一篇帖子。嗯，我觉得可以给个头秃（虽然不是比赛）：
忘穿秋裤的回复套路，可以发现没有剪辑的痕迹，所以你懂得：
事实上忘穿秋裤已经被榨干了（BUSHI
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文：
第一部分，算法讲解。
先来讲讲迪杰斯特拉的创作背景吧。（内容参考了AI总结）：
迪杰斯特拉在195619561956-195919591959年设计该算法时，主要目的是解决荷兰东部城市鹿特丹到格罗宁根的汽车路线规划问题。这一需求推动了算法的诞生，其核心在于通过贪心策略和优先队列优化实现高效路径计算。
迪杰斯特拉是求单源最短路径的一个算法，整体采用了贪心\color{red}贪心贪心的策略。该算法可以通过优先队列进行优化，本帖只讲他未优化的用邻接矩阵实现的算法（其实是不会写优化(doge）。如果不知道邻接矩阵怎么写可以在帖子下方评论，我会考虑写一个简单的邻接矩阵的讲解，但是就不标创人计划了。
先 口胡 口头讲解一下。从起点出发，首先将起点设为 000 ,其他点设为无限[1]。将当前点标记为已走过，遍历当前节点的相邻点，我们可以计算出：
设 kkk 为当前节点的最短路径，www 为遍历到此节点所计算出的路径，该节点这一轮遍历的结果为：
min(k,w)min(k,w) min(k,w)
遍历完所有相邻点时，我们在其相邻节点中选择路径最短的点，重复上述操作，知道所有节点遍历完成。迪杰斯特拉算法的时间复杂度是 O(n2)O(n^2)O(n2) 。需要特别注意，迪杰斯特拉算法无法\color{red}无法无法处理负权边[2]，具体原因见我下面的讲解。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注：红色部分为初始化内容，其余部分为正式遍历
1.\color{red}1.1. 好的，保留节目，我画了一个简单的有向图，用于模拟迪杰斯特拉算法的实现过程。同时，我直接按照上面我讲的初始化了。同时，为了防止你们眼睛x掉，我特意用了3天换了个材质
2.\color{red}2.2.从起点开始，初始化[3]。输入这个图，构建邻接矩阵。
1. 正式开始遍历。先从节点 AAA 开始遍历，A的邻居顶点有 BBB 和 CCC 。从 AAA 到 BBB 的距离为 222 ，因为 2<无穷2 < 无穷2<无穷 , 所以我们把 disdisdis 数组中 BBB 的位置设为 222 。按照上述操作，将 disdisdis 数组中的 CCC 设为 555 。
2. 如图，可得 AAA 相邻的节点中， BBB 的距离是最短的，所以我们从节点AAA开始遍历节点 BBB 。
按照上述方法遍历节点 BBB 的相邻节点。当前节点路径长度为前一个节点的路径长度加上边的权值。所以我们可得在 disdisdis 数组中， DDD 的数值为 333 ， EEE 的数值为 888 。同时，将节点 BBB 设为已访问。
3. 这样节点 BBB 的遍历就完成了。在 disdisdis 数组中寻找未访问且当前路径最短的节点，可以发现是节点 DDD 。那么我们从节点 BBB 到节点 DDD 。
4.更新节点 DDD 的所有邻居节点的当前最短路径。这里不详细解释了。同时记得把 DDD 标记为已访问。
5.可以发现节点 EEE 的最短路径从 888 变为了 444 。节点 FFF 的最短路径从无穷变为了 999 。那么节点 DDD 就遍历完成了。寻找路径最短且未被访问过的顶点，为节点 EEE。那么从节点 EEE 开始访问。这里不做详细解释。
6.顶点 GGG 的最短路径从无穷变为了 141414。选择当前路径最短且未访问的顶点 CCC 。 CCC 没有邻居，将 CCC 设为已访问。寻找下一个符合要求的节点，为节点 FFF 。
7.从节点 FFF 开始遍历，节点 GGG 的最短路径从 141414 变为了 101010 。
8.最后访问终点 GGG 。没有可访问的节点。那么该图的迪杰斯特拉算法结束。通过 disdisdis 数组可得每个节点的在最短路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二部分：代码解析：
首先我们要初始化。详见[3:1]。
接下来开始遍历所有节点，这是一个大 forforfor 循环。我们先选择当前所要遍历的节点 uuu 。
开始遍历 uuu 的邻居节点。如果有这个节点，我们更新[4]该节点。
综上所述，迪杰斯特拉的核心代码为：
最后，整体代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第三部分，真题演练。
先看题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让 SPFA 不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,sn,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 mmm 行每行包含三个整数 u,v,wu,v,wu,v,w，表示一条 u→vu \to vu→v 的，长度为 www 的边。
输出格式
输出一行 nnn 个整数，第 iii 个表示 sss 到第 iii 个点的最短路径，若不能到达则输出 231−12^{31}-1231−1。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
【数据范围】
对于 20%20\%20% 的数据：1≤n≤51\le n \le 51≤n≤5，1≤m≤151\le m \le 151≤m≤15；
对于 40%40\%40% 的数据：1≤n≤1001\le n \le 1001≤n≤100，1≤m≤1041\le m \le 10^41≤m≤104；
对于 70%70\%70% 的数据：1≤n≤10001\le n \le 10001≤n≤1000，1≤m≤1051\le m \le 10^51≤m≤105；
对于 100%100\%100% 的数据：1≤n≤1041 \le n \le 10^41≤n≤104，1≤m≤5×1051\le m \le 5\times 10^51≤m≤5×105，1≤u,v≤n1\le u,v\le n1≤u,v≤n，w≥0w\ge 0w≥0，∑w<231\sum w< 2^{31}∑w<231，保证数据随机。
Update 2022/07/29：两个点之间可能有多条边，敬请注意。
对于真正 100%100\%100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
图片 1 到 3 和 1 到 4 的文字位置调换。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这道题我们的代码是过不了的。事实上，你提交的时候只会得70分或60分。因为正解是邻接表。
很简单，板子题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
再看一道。
题目和上面一样，不过变成了无向图。这里就不搬了。
那么无向图怎么做？
和有向图一样。disdisdis 函数是不变的。但是，在输入的时候我们要考虑这一问题。可以发现在邻接矩阵中，无向图会有两边的储存。比如 mp[u][v] 与 mp[v][u] 是一样的。但是有向图中这两个位置的值有一个是 000 。所以我们只要输入双向边即可。这里做了重边处理：
那么本帖就到这里结束了，谢谢各位的观看
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本贴如有错误，请私信贴主。
彩蛋：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二篇\HUGE{第二篇}第二篇 第二篇→
注解：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 在c++中，无限可以用0x3f3f来表示，你可以不断地加上3f，但是建议你叠加时不要超过八个3f（即0x3f3f3f3f3f3f3f3f ），在往上叠加就没用了，而且可能会CE。 ↩︎
2. 即边的权值为负的边 ↩︎
3. 将$ dis$ 数组中除起点外的其他点设为无穷，起点设为 000 。visvisvis 数组中讲起点设为 111 ，其余点设为 000 。即已访问与未访问。 ↩︎ ↩︎
4. 检查 uuu 点到该点的距离，如果小于原本该点的距离，则更新为点 uuu 的距离加上节点之间边的权值 www 。 ↩︎
有帮助，赞一个