(1) Floyd
时间复杂度：\(O(n^3)\)
全源最短路
可处理负边权
upd on 2021/10/7：
把原邻接矩阵看作一个矩阵。
与广义矩阵乘法的结合律完美地契合。
模板：
//dis[i][j]表示：经由编号k或k之前的点，从i到j的最短路径
for(int k=1;k<=n;k++)//k枚举中转点*
for(int i=1;i<=n;i++)//起点
for(int j=1;j<=n;j++)//终点
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
*中转点：可以利用的点，并且可以按照其他顺序（如时间轴）枚举（参见灾后重建）
(2) Bellman-Ford
时间复杂度：O(nm)
思路：没有什么最短路问题是松弛解决不了的，如果有，那就来n-1次
模板：
for(int i=1;i<=n-1;i++){//松弛次数
for(int j=1;j<=m;j++){//枚举每条边
dis[v[j]]=min(dis[v[j]],dis[u[j]]+w[j]);
}
}
而且还能判负环
for(int j=1;j<=m;j++){
if(dis[f[j][2]]>dis[f[j][1]]+f[j][3])
return 有负环;
}
return 那没事了;
而且还有小小的优化（不是SPFA）
for(int i=1;i<=n-1;i++){
bool chk=0;
for(int j=1;j<=m;j++){
if(dis[v[j]]>dis[u[j]]+w[j]){
chk=1;
dis[v[j]]=dis[u[j]]+w[j];
}
}
if(!chk)break;
}
//就是说，如果这一轮都一次都没有松弛，那以后就更不可能去松弛了
(3)the dead SPFA
是贝尔曼的优化版，省去了无用点的松弛
时间复杂度：\(O(kn)\)
可以用来求最长路礼貌拓扑：你吗
模板：
while(!q.empty()){//当队列非空
int u=q.front();//把队首揪出来
q.pop();
vis[u]=0;
for(int i=head[u];i!=0;i=edge[i].next){//枚举从i出发的每条边
int v=edge[i].to;//终点
int w=edge[i].dis;//边权
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;//松弛
if(!vis[v]){
vis[v]=1;
q.push(v);//入队
}
}
}
}
}
注：据rings(巨佬%%%)所说，“会死的很惨”。所以有了全源最短路。（update on 2021/6/15）
(4)Dijkstra
注：不能处理负边权（是建立在贪心基础上的算法）
朴素版时间复杂度：O(n^2)每次找到最近的点，因为它不可能被更短的路径松弛了
堆优化
时间复杂度：O((n+m)logn)
思路：
“未知的最近的终点”
维护一个堆只用logn即可
就可以省下不少时间
1、建立小根堆
struct node
{
int dis;
int pos;
bool operator <( const node &x )const{
return x.dis<dis;
}
};
priority_queue<node> q;
Dijkstra
while(!q.empty()){//堆中有点
node tmp=q.top();q.pop();
int u=tmp.pos; //取堆顶。
if(vis[u])continue;vis[u]=1;
for(int i=head[u]; i!=0; i=edge[i].next){//从这个点开始松弛
int v=edge[i].to;
int w=edge[i].dis;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push((node){dis[v], v});//维护未知点的小根堆
}
}
}
}
(5)其它
1、这道题
正解：二分（限制可用点）+ 最短路
2、关于边权与状态转移
这道题把没毁坏的路标记为无穷大；
这道题贪一波就会发现不能走重复点，并且边权为布尔型
这道题由于边权为手续费，状态转移很特殊，是dis[]*(1-r[][])
update on 2021/6/15：同余最短路，差分约束，分层图最短路，全源最短路
同余最短路
以同余为转化手段，构建关于最短路的条件，解决特定情境下的问题。
例：跳楼机
乍一看，哦！这不是我可爱的完全背包么！
再一看，哦！这不是我可爱的MLE么！
......
略一想，哦！该请出我们可爱的最短路了！
1.以同余为转化手段
下面设x（第一种操作跳的层数）为基准数。
设dis[i]表示仅用y、z两种手段，跳到第( k x + i )层时（即模x为i的层数），所跳到的最低的层数。（显然i：0 -> x-1）
注意理解，实在不懂的话往下看然后回来手模样例
所以，最终的答案就是Σ( h - dis[i] ) / x + 1，(i：0 -> x-1 )&& ( dis[i] <= h )
下文有解释，记得手模样例
例：h=10 ; x=3 ; y=4 ; z=5 .
因为从第一层出发，所以dis[1]=1;
dis[0]=6,因为要想从第1层走到第k层，使（k%x0），至少需要跳z层到达第六层。
同理，dis[2]=5。
因为dis[1]=1，所有从1到h的楼层中，只要%x1的就都能到达。
因为dis[0]=6，所有从6到h的楼层中，只要%x0的就都能到达。
因为dis[2]=5，所有从5到h的楼层中，只要%x2的就都能到达。
对于每一项dis，对答案贡献的楼层数是( h - dis[i] ) / x + 1。
不同dis[i]的贡献不可能重复，因为同一个数%x只有同一个值。 废话
注：为节省空间，选基准数时尽量选最小数。
2.构建关于最短路的条件
转化，把不同的dis之间建边，边权即为每次跳的楼层数。
很好理解，放个代码一下就懂了
for(int i=0;i<x;i++){
//add(起，终，边权);
add(i,(a[2]+i)%x,a[2]);
add(i,(a[3]+i)%x,a[3]);
}
然后跑最短路即可。
关于边界：设初始值为初始值即可。
3.特定情境下的问题
有个公式的，这里由于不会用LaTeX 懒 就不讲了，参见墨墨的等式
差分约束
再咕一会
参见博客
分层图最短路
自己去看飞行路线的题解吧，懒得讲了。
还有冻结、最优贸易、
回家的路。
注：回家的路：建边时有个小小的思维点需要仔细考虑。
下面是抄来的题解。
Q:为什么要用分层图最短路？
A:在一个正常的图上可以进行 k 次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边，表示付出该代价后就可以转换状态了。
———原文链接
那么接下来就是写法&分析关键点。
1、写法
1）真 · 建 k 层图，直接跑最短路。（有手就行不长脑袋）（建边时仔细分析层层关系即可）
有边的两个点，多建一条到下一层边权为0的单向边，如果走了这条边就表示用了一次机会。
有N个点时，1n表示第一层，（1+n）（n+n）代表第二层，（1+2n）（n+2*n）代表第三层，（1+i*n）（n+in）代表第i+1层。
因为要建K+1层图，数组要开到n * ( k + 1)，点的个数也为n * ( k + 1 ) 。
———原文链接
2）D · 分层图 · P 写法，省下建一堆边的空间
据说，
我们把dis数组和vis数组多开一维记录k次机会的信息。
dis[ i ][ j ] 代表到达 i 用了 j 次免费机会的最小花费.
vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.
更新的时候先更新同层之间（即花费免费机会相同）的最短路，然后更新从该层到下一层（即再花费一次免费机会）的最短路。———原文链接
对于每个点，可以用一个结构体存下：p和pos，表示第几层的第几个点。
至于松弛，基本是一样的。
if(dis[v][p]>dis[u][p]+w){
dis[v][p]=dis[u][p]+w;
q.push((node){v,p,dis[v][p]});
}
if(p>=k)continue;
if(dis[v][p+1]>dis[u][p]+w/2){
dis[v][p+1]=dis[u][p]+w/2;
q.push((node){v,p+1,dis[v][p+1]});
}
2、关键
1）分析层与层关系。
如，对于飞行路线，要将每条边的边权变成0连向下一层；
对于冻结，要将每条边的边权变成一半连向下一层；
对于回家的路，要做“面的垂线”，边权为一并且可以从第二层返回第一层。
2）明确最终答案与初始值。
最终答案：
对于最优贸易，答案为第三层与第一层任选；
对于其余，答案均为所有层任选。
初始值：
有的为仅初始化第一层，有的初始化所有层。
全源最短路
来源于某巨佬的提醒。
至于做法，题解讲得很清楚，这里仅在大板块下做一个梳理。
.
upd on 2021/8/4:分层图同余最短路
同余最短路一般都是裸题，看出来算法就基本上切掉了。。。
但是题目中有时会加上诸如 “选不超过c个物品” 的限制
这不就是分层图吗
我们按同余最短路的套路建图，再加一维表示用了几个物品。
跑分层图即可，一般不用建边。