点个赞评个论喵。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
常见最短路
01BFS\mathtt{01BFS}01BFS 是一种单源最短路算法。
解决边权为 0,10,10,1 的最短路问题。
采用 BFS\mathtt{BFS}BFS 解决,可以证明最先到达的一定是最短路。
该算法维护一个距离数组 disdisdis,disidis_idisi 表示为 sss 至 iii 的最短距离。
Dijkstra\mathtt{Dijkstra}Dijkstra 是一种单源最短路算法。
解决非负权边的最短路问题。
采用贪心策略,每次访问离 sss 最近且未被访问的顶点,直至扩展完所有点。
该算法维护一个距离数组 disdisdis,disidis_idisi 表示为 sss 至 iii 的最短距离。
Bellman−Ford\mathtt{Bellman-Ford}Bellman−Ford 是一种单源最短路算法。
解决任意权边的最短路问题。
进行 nnn 次循环,每次前进一步,判断经过的边是否因此而有更优松弛。
该算法维护一个距离数组 disdisdis,disidis_idisi 表示为 sss 至 iii 的最短距离。
SPFA\mathtt{SPFA}SPFA 是一种单源最短路算法。SPFA已死,此BF当立之时。\color{white}{\mathtt{SPFA} 已死,此 \mathtt{BF} 当立之时。}SPFA已死,此BF当立之时。
解决任意权边的最短路问题。
是 Bellman−Ford\mathtt{Bellman-Ford}Bellman−Ford 的优化。
采用队列进行,对于所有上轮仍在更新的点进行松弛。
该算法维护一个距离数组 disdisdis,disidis_idisi 表示为 sss 至 iii 的最短距离。
Floyd\mathtt{Floyd}Floyd 是一种全源最短路算法。
解决任意权边的最短路问题。
对于可能出现松弛的情况进行完整的枚举。
该算法维护一个距离数组 disdisdis,disi,jdis_{i,j}disi,j 表示从 iii 到 jjj 的最短距离。
判断负环:
1.SPFA\mathtt{SPFA}SPFA 对于一个点跑了不少于 n+1n+1n+1 次。
2.Floyd\mathtt{Floyd}Floyd 中有 disi,i<0dis_{i,i} < 0disi,i <0。
例题 P4011
我们发现每次移动所耗费时间相同,采用 01BFS\mathtt{01BFS}01BFS 解决。
由于 PPP 非常小,考虑状压所拥有钥匙情况。
注意实现细节即可。即:起点可能会有钥匙 一个位置可能有多个钥匙等
例题 P8817
注意到 O(n2)O(n^2)O(n2) 的时间复杂度可以通过。
我们枚举 B−CB-CB−C,预处理 A,DA,DA,D。
显然预处理每个点所有可以 kkk 步通达的点中权值前 ppp 大的点所需的时间是 O(n2p)O(n^2p)O(n2p)。
为防止重复,选择最大、次大和次次大的点,可以证明的是,这样一定能保证不重复。
时间复杂度约为 O(n2)O(n^2)O(n2),可以通过。
代码没写。