掐指一算，上一次学图论可能还是在学 MST 的时候，以至于连 dij 都忘得差不多了。

两年来欠下的债好多啊，要慢慢还了/kk

1. 最短路

1.1 Bellman-Ford

你看确实是从零开始吧。

其实挺暴力的，就是不断更新最短路就行。

具体地，对于每一条边 \((u,v)\)，用 \(d_u+w_{u,v}\) 更新 \(d_v\)。每次至少有一个节点的最短路被更新，那么松弛 \(n-1\) 次即可。

正确性证明：假设源点为 \(1\)。那么在 \(1\to u\) 的最短路 \(1\to p_1\to\cdots\to u\) 中，对于每一个节点 \(p_i\)，\(1\to p_1\to\cdots\to p_i\) 也一定是 \(1\to p_i\) 的最短路。所以一个节点的最短路一定是由另一个节点的最短路扩展而来的。因为最短路最多有 \(n-1\) 条边，而第 \(i\) 次松弛会得到边数为 \(i\) 的最短路，故最多只要松弛 \(n-1\) 次。

此外该算法还可以用来判负环：如果在第 \(n\) 次松弛时仍有节点的最短路被更新，那么存在负环。

时间复杂度 \(\mathcal{O}(nm)\)。

本来想学一个 SPFA，但是为什么要学一个死掉的算法呢？

1.2. Dijkstra

基于贪心的最短路算法，适用于非负权图。

在已经得到最短路的节点中，取出没有扩展过的距离最小的节点并扩展。因为没有负权边，所以取出的节点的最短路长度单调不降。正确性显然。

取出距离最小节点的过程一般用优先队列 priority_queue。

1.3. Johnson 全源最短路径

前置知识：Bellman-Ford & Dijkstra。

建一个虚拟节点 \(0\) 并向剩余所有节点连一条边权为 \(0\) 的边，一次 Bellman-Ford 跑出 \(0\to i\) 的最短路 \(h_i\)。

接着把每条边赋值为 \(w_{u,v}+h_u-h_v\)，得到的新图与原图任意两点间的最短路径不变，同时没有负边权，可以使用 dijkstra，最后不要忘了将 \(u\to v\) 的最短路加上 \(h_v-h_u\)。

实际上，如果给每个点随机赋值 \(val_i\) 并把每条边赋值为 \(w_{u,v}+val_u-val_v\)，任意两点间的最短路径都是不变的
。而预先跑一次 BF 算法的目的，是为了通过三角形不等式保证新边权非负。

时间复杂度 \(\mathcal{O}(nm\log m)\)。

模板题 P5905 代码。

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair <int,int>
#define fi first
#define se second

const int N=3e3+5;
const ll inf=1e9;

ll n,m,h[N],dis[N],ans;
vector <pii> e[N];

void BF(){
	memset(h,0x3f,sizeof(h)),h[0]=0;
	for(int i=0,upd;i<=n;i++){
		upd=0;
		for(int j=0;j<=n;j++)
			for(pii it:e[j])
				if(h[it.fi]>h[j]+it.se)
					upd=1,h[it.fi]=h[j]+it.se;
		if(i==n&&upd)puts("-1"),exit(0);
	}
}

priority_queue <pii,vector<pii>,greater<pii> > q;
void dij(int s){
	memset(dis,0x3f,sizeof(dis)),q.push({dis[s]=0,s});
	while(!q.empty()){
		pii t=q.top(); q.pop();
		int id=t.se,ds=t.fi;
		if(dis[id]<ds)continue;
		for(pii it:e[id]){
			int d=ds+it.se+h[id]-h[it.fi];
			if(dis[it.fi]>d)q.push({dis[it.fi]=d,it.fi});
		}
	} for(int i=1;i<=n;i++)ans+=min(dis[i]-h[s]+h[i],inf)*i;
	cout<<ans<<endl,ans=0;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)e[0].push_back({i,0});
	for(int i=1;i<=m;i++){
		int u,v,w; cin>>u>>v>>w;
		e[u].push_back({v,w});
	} BF();
	for(int i=1;i<=n;i++)dij(i);
	return 0;
}

1.4 k 短路

堆的可持久化。

妈耶，看不太懂论文啊。