板子是一定要记的，但不够，全是思维题，要解放思想开动脑筋。
板子
Floyd
是全源最短路。
只要最短路存在（无负环），不管有向无向，边权正负，都可以用。
板子
for(int k=1;k<=n;++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]);
\\dis[k][i][j]=min(dis[k-1][i][j],dis[k-1][i][k]+dis[k-1][k][j]);
}
}
本质是一个DP。
\(O(n^3)\)
Dijkstra
是单源最短路。
只适用于非负权图
-
暴力做\(O(n^2)\)（适合稠密图）
-
线段树/二叉堆优化\(O(m\log n)\)（适合稀疏图）
-
堆优化\(O(m\log m)\)（适合稀疏图）
堆优化板子（最好写的一个）
priority_queue< pair<int,int> > q;//默认的是大根堆，所以下方dis[v]取相反数。
scanf("%d%d",&s,&t);
for(int i=0;i<=n;++i) dis[i]=inf;
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
暴力板子
for(int u=1;u<=n;u++){
dis[u]=inf;
vis[u]=false;
}
dis[s]=0;
for(int i=1;i<=n;i++){
int minx=inf,u=0;
for(int v=1;v<= n;v ++){
if(vis[v]||dis[v]>minx) continue;
minx=dis[v],u=v;
}
vis[u]=1;
for(int j=head[u];j;j=e[j].nxt){
int v=e[j].v,w=e[j].w;
if(dis[v]<dis[u]+w) continue;
dis[v]=dis[u]+w;
}
}
线段树优化板子
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10,inf=1e9+7;
int n,m,tot,s,head[maxn],dis[maxn],mi[maxn<<2];
struct edge{
int v,w,nxt;
}e[maxm];
void add(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
#define ls(k) k<<1
#define rs(k) k<<1|1
void pushup(int k){
mi[k]=min(mi[ls(k)],mi[rs(k)]);
}
void build(int k,int l,int r){
mi[k]=inf;
if(l==r) return;
int mid=l+r>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
pushup(k);
}
void upd(int k,int l,int r,int p,int v){
if(l==r){
mi[k]=v;
return;
}
int mid=l+r>>1;
if(p<=mid) upd(ls(k),l,mid,p,v);
else upd(rs(k),mid+1,r,p,v);
pushup(k);
}
int query(int k,int l,int r){
if(l==r) return l;
int mid=l+r>>1;
if(mi[ls(k)]<=mi[rs(k)]) return query(ls(k),l,mid);
else return query(rs(k),mid+1,r);
}
\\其实就是用线段树做优先队列在做的事情。
\\线段树维护的是还未确定最短路的集合，inf即可以表示已经被移出了该集合，也可以表示最开始初始化的最短路长度。
\\每次移出该集合中最短路最小的点，并用这个点的出边进行松弛操作。
void dijkstra(){
for(int i=1;i<=n;++i) dis[i]=inf;
build(1,1,n);
upd(1,1,n,s,0);
dis[s]=0;
while(mi[1]^inf){
int u=query(1,1,n);
upd(1,1,n,u,inf);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
upd(1,1,n,v,dis[v]);
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dijkstra();
for(int i=1;i<=n;++i) printf("%d ",dis[i]);
return 0;
}
Bellman-Ford和SPFA
这两个都可以处理带负权的图上的最短路，并且可以判断最短路是否存在（判断负环）
SPFA是Bellman-Ford的队列优化。
Bellman-Ford是在每轮循环中对每条边尝试松弛，每轮松弛至少使最短路长度\(+1\)，所以最多进行\(n-1\)轮。\(O(nm)\)。
显然只有在上一次被松弛过的点所连的边才可能引起下次松弛，用队列存一下，每次只松弛必要的边，就得到了SPFA。
SPFA大多数时候跑得比较快，但最坏\(O(nm)\)，要小心使用尽量别用。SPFA容易被卡，但费用流要用。
判断负环：记录一下最短路经过了几条边，当最短路至少经过\(n\)条边时，就说明可以抵达负环（因为如果没有负环，最短路最多经过\(n-1\)条边）。
注意这里只能判断从起点\(s\)出发能否抵达负环。若图不保证连通，要判断是否存在负环，则要建立一个超级源点\(S\)，从\(S\)向每个点连边（边权为\(0\)），再跑SPFA。
SPFA判断负环板子
bool spfa(int n, int s){
for(int i=1;i<=n;++i) dis[i]=inf;
dis[s]=0,inque[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
inque[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v, w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=n) return false;
if(!inque[v]) q.push(v), inque[v]=1;
}
}
}
return true;
}
Johnson
能处理无负环图上的全源最短路。
流程：
- 建立超级源点\(S\)向每个点连边，边权为\(0\).
- 以\(S\)为起点跑一遍SPFA，求出到每个点\(i\)的最短路\(h_i\)
- 对于一条起点为\(u\)，终点为\(v\)，边权为\(w\)的边，重新设置边权为\(w+h_u-h_v\)。
- 这样就保证了边权非负，以每个点为起点跑\(n\)轮Dijkstra即可。
- 最终求出\(u\)到\(v\)的最短路为\(dis_{u,v}\)，则原来\(u\)到\(v\)的最短路为\(dis_{u,v}+h_v-h_u\)。若\(dis_{u,v}=inf\)，则\(u\)不可到达\(v\)。
当Dijkstra使用堆优化时，Johnson的时间复杂度为\(O(nm\log m)\)，在稀疏图上比Floyd好。
板子
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e3+10,maxm=6e3+10,inf=1e9;
int n,m,tot=0,head[maxn],cnt[maxn];
bool vis[maxn];
ll ans=0,dis[maxn],h[maxn];
struct edge{
int u,v,w,nxt;
}e[maxm+maxn];
void add(int u,int v,int w){
e[++tot].u=u;
e[tot].v=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
void spfa(){
memset(h,0x3f3f3f3f,sizeof h);
queue<int> q;
h[0]=0,vis[0]=true;
q.push(0);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(h[v]>h[u]+w){
h[v]=h[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>n){
puts("-1");
exit(0);
}
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
}
}
void dijkstra(int s){
for(int i=1;i<=n;++i) vis[i]=false,dis[i]=inf;
dis[s]=0;
priority_queue< pair<ll,int> > q;
q.push(make_pair(0,s));
while(!q.empty()){
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(int i=1;i<=n;++i) add(0,i,0);
spfa();
for(int i=1;i<=tot;++i){
int u=e[i].u,v=e[i].v;
e[i].w+=h[u]-h[v];
}
for(int i=1;i<=n;++i){
dijkstra(i);
ans=0;
for(int j=1;j<=n;++j){
if(dis[j]==inf) ans+=1ll*j*inf;
else ans+=1ll*j*(dis[j]+h[j]-h[i]);
}
printf("%lld\n",ans);
}
return 0;
}