【模板】图论 最短路 (Floyd+SPFA+Dijkstra)

Floyd+SPFA+Dijkstra

温故而知新，这三种算法都是求最短路问题常用的算法（特别是Dijkstra)

1.Floyd （多源最短路）

基于动态规划思想，时间复杂度为 $O(N^3)$ 较高。
注意点： 初始化距离为INF，k（中介结点）一定在循环最外层

void Floyd(){for(int k = 1;k <= n; ++k)for(int i = 1;i <= n; ++i)for(int j = 1;j <= n; ++j)f[i][j] = min(f[i][j],f[i][k]+f[k][j]);
}

2.SPFA (处理负权回路)

SPFA算法就是bllman_ford算法加上了队列优化，能够处理负权边。
最坏情况下的时间复杂度为$O(NM)$,容易被卡成啥币，所以要谨慎使用（在没有负权边时最好使用 Dijkstra 算法）

流程：用dis数组记录源点到有向图上任意一点距离，其中源点到自身距离为0，到其他点距离为INF。将源点入队，并重复以下步骤：

• 队首t出队，并将t标记为没有访问过，方便下次入队松弛
• 遍历所有以队首为起点的有向边$(t,j)$，若$dis[j]>dis[t]+w(t,j)$，则更新$dis[j]$
• 如果点$j$不在队列中(未被标记)，则$j$入队，并将j标记为访问过
• 若队列为空，跳出循环；否则执行第一步

//判负环 ： cnt记录循环次数，如果达到n，说明进入负环。
const int N = 2e6+10;
int n,m,q;
vector<PII> E[N];
int dis[N],cnt[N];
bool vis[N];
void spfa(){queue<int> que;for(int i = 1;i <= n; ++i) que.push(i),vis[i] = true;while(!que.empty()){int t = que.front();que.pop();vis[t] = false;//表明t这个点已经离开这个队列了for(int i = 0,l = E[t].size();i < l; ++i) {int j = E[t][i].first,k = E[t][i].second;if(dis[j] > dis[t] + k) {dis[j] = dis[t] + k;cnt[j] = cnt[t] + 1;if(cnt[j] >= n) {//找到负权回路cout<<"Yes"<<endl;return;}if(!vis[j])//将j这个点重新加入队列que.push(j),vis[j] = true;}}}cout<<"No"<<endl;
}

3.Dijkstra （单源最短路，适用于非负权图）

dijkstra是一种基于贪心的单源最短路径算法, 时间复杂度 ：
朴素： $O(n^2)$ 在稠密图上效率更高
优先队列/堆优化 : $O((n+m){\log }_{2}n)$ 在稀疏图上效率更高
不适用于处理负权图，遇到负权图时可以考虑SPFA算法
路径打印：使用pre[]数组，记录最短路的上一个结点。

//朴素DJ：
int f[N][N],n,m,dis[N];
bool vis[N];void DJ(int s){for(int i = 1;i <= n; ++i) dis[i] = INF,vis[i] = false;dis[s] = 0;for(int i = 1;i <= n; ++i) {int t = -1;for(int j = 1;j <= n; ++j) if(!vis[j] && (t == -1 || dis[j] < dis[t])) t = j;if(t == -1) return;vis[t] = true;for(int j = 1;j <= n; ++j)if(dis[j] > dis[t] + f[t][j])dis[j] = dis[t] + f[t][j];}
}//优先队列优化DJ：
const int N = 2e6+10;
int dis[N],n,m;
bool vis[N];
vector<PII> E[N];void DJ(int s){for(int i = 1;i <= n; ++i) dis[i] = INF,vis[i] = false;priority_queue<PII,vector<PII>,greater<PII> > que; //小根堆que.push({0,s});dis[s] = 0;while(!que.empty()){int t = que.top().second;que.pop();if(vis[t]) continue;vis[t] = true;for(int i = 0,l = E[t].size();i < l; ++i) {int j = E[t][i].first,w = E[t][i].second;if(dis[j] > dis[t] + w){dis[j] = dis[t] + w,que.push({dis[j],j});}}}
}

实战演练：森森旅游

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define PII pair<int,int>
#define FU(i, a, b) for(int i = (a); i <= (b); ++ i)
#define FD(i, a, b) for(int i = (a); i >= (b); -- i)
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5+10;int disa[N],disb[N],n,m,q;
bool vis[N];
vector<PII> Ez[N];
vector<PII> Ef[N];
int k[N];void DJ(int s,vector<PII> (&E)[N],int (&dis)[N]){for(int i = 1;i <= n; ++i) dis[i] = INF,vis[i] = false;priority_queue<PII,vector<PII>,greater<PII> > que; //小根堆que.push({0,s});dis[s] = 0;while(!que.empty()){int t = que.top().second;que.pop();if(vis[t]) continue;vis[t] = true;for(int p = 0,l = E[t].size();p < l; ++p) {int j = E[t][p].first,w = E[t][p].second;if(dis[j] > dis[t] + w){dis[j] = dis[t] + w,que.push({dis[j],j});}}}
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);cin>>n>>m>>q;for(int i=0;i<m;i++){int u,v,c,d;cin>>u>>v>>c>>d;Ez[u].pb({v,c}); //正向存边：现金Ef[v].pb({u,d}); //反向存边：旅游金}for(int i=1;i<=n;i++){cin>>k[i];}DJ(n,Ef,disb);//反向DJ disb 从x点到n点的最小旅游金DJ(1,Ez,disa);//正向DJ disa 从1点到x点的最小现金// for(int i=1;i<=n;i++){// 	cout<<disa[i]<<" "<<disb[i]<<endl;// }multiset<int> S; //用multiset存在每个城市兑换的ans，for(int i=1;i<=n;i++){if (disa[i] != INF && disb[i] != INF){S.insert(disa[i]+(disb[i]+k[i]-1)/k[i]);}}for(int i=0;i<q;i++){int a,b;cin>>a>>b;if (disa[a] != INF && disb[a] != INF){S.erase(S.find(disa[a]+(disb[a]+k[a]-1)/k[a]));}k[a]=b;if (disa[a] != INF && disb[a] != INF){S.insert(disa[a]+(disb[a]+k[a]-1)/k[a]);}cout<<*S.begin()<<endl;}return 0;
}