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

Floyd+SPFA+Dijkstra

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

1.Floyd （多源最短路）

基于动态规划思想，时间复杂度为 O ( N 3 ) O(N^3) O(N3) 较高。 注意点： 初始化距离为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 ( N M ) O(NM) O(NM),容易被卡成啥币，所以要谨慎使用（在没有负权边时最好使用 Dijkstra 算法）

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

队首t出队，并将t标记为没有访问过，方便下次入队松弛遍历所有以队首为起点的有向边 ( t , j ) (t,j) (t,j)，若 d i s [ j ] > d i s [ t ] + w ( t , j ) dis[j]>dis[t]+w(t,j) dis[j]>dis[t]+w(t,j)，则更新 d i s [ j ] dis[j] dis[j]如果点 j j j不在队列中(未被标记)，则 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^2) O(n2) 在稠密图上效率更高 优先队列/堆优化 : O ( ( n + m ) log ⁡ 2 n ) O((n+m)\log_{2}n) O((n+m)log2​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; }