【模板】图论 最短路 (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;
}