当前位置：首页 > news >正文

最短路拓展

news 2026/6/16 14:36:23

最短路拓展

0X01 分层图最短路

题目

我们可以把这种有 $k$ 次把 $(u,v)$ 改变成 $w$ 题目叫做 分层图最短路

你还记得 Dijkstra 吗对!我们可以仿照 Dijkstra 的思路从起点 $s$ 开始跑一遍最短路然后返回 $l_t$

但有个问题来了我们有 $k$ 次改变边权的机会啊

那我们是不是可以把改变了 $a$ 次后的图存下来在和改变 $a-1$ 后的图拼接起来呢

没错这就是分层图最短路 可能单说理解不了那看 code

code:

//LG
//[JLOI2011] 飞行路线
//https://www.luogu.com.cn/problem/P4568
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct e{int u,v;int w;
};
vector<e> G[110010];
int n,m,k,s,t;
int Dijkstra(int s,int t){vector<int> l(n*(k+1)+10,INT_MAX);l[s]=0;vector<bool> f(n*(k+1)+10,1);priority_queue<pair<int,int> > q;q.push(make_pair(0,s));while(q.size()){int u=q.top().second;q.pop();if(f[u]){f[u]=0;for(int j=0;j<G[u].size();j++){int v=G[u][j].v,w=G[u][j].w;if(l[v]>l[u]+w){l[v]=l[u]+w;q.push(make_pair(-l[v],v));}}}}int ans=INT_MAX;for(int i=0;i<=k;i++)ans=min(ans,l[t+i*n]);return ans;
}
int main(){cin>>n>>m>>k;cin>>s>>t;while(m--){int u,v,w;cin>>u>>v>>w;for(int i=0;i<=k;i++){G[u+i*n].push_back({u+i*n,v+i*n,w});G[v+i*n].push_back({v+i*n,u+i*n,w});}for(int i=0;i<k;i++){G[u+i*n].push_back({u+i*n,v+(i+1)*n,0});G[v+i*n].push_back({v+i*n,u+(i+1)*n,0});}}cout<<Dijkstra(s,t);return 0;
}

可以看到整个 Dijkstra 是没有变的重要的部分是

for(int i=0;i<=k;i++){G[u+i*n].push_back({u+i*n,v+i*n,w});G[v+i*n].push_back({v+i*n,u+i*n,w});
}
for(int i=0;i<k;i++){G[u+i*n].push_back({u+i*n,v+(i+1)*n,0});G[v+i*n].push_back({v+i*n,u+(i+1)*n,0});
}

这就是新建改变了 $a$ 次后的图再和改变 $a-1$ 后的图拼接起来

除了这种解法还有一种DP的解法不太会用到就不讲了有兴趣可以看看我写的 code

code:

//LG
//[JLOI2011] 飞行路线
//https://www.luogu.com.cn/problem/P4568
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct e{int u,v;int w;
};
vector<e> G[110010];
int n,m,k,s,t;
int Dijkstra(int s,int t){vector<vector<int> > l(n+10,vector<int>(k+1,INT_MAX));l[s][0]=0;vector<vector<bool> > f(n+10,vector<bool>(k+1,1));priority_queue<pair<int,pair<int,int> > > q;q.push(make_pair(0,make_pair(s,0)));while(q.size()){int u=q.top().second.first,cnt=-q.top().second.second;q.pop();if(f[u][cnt]){f[u][cnt]=0;for(int j=0;j<G[u].size();j++){int v=G[u][j].v,w=G[u][j].w;if(l[v][cnt]>l[u][cnt]+w){l[v][cnt]=l[u][cnt]+w;q.push(make_pair(-l[v][cnt],make_pair(v,-cnt)));}if(cnt<k&&l[v][cnt+1]>l[u][cnt]){l[v][cnt+1]=l[u][cnt];q.push(make_pair(-l[v][cnt+1],make_pair(v,-(cnt+1))));}}}}int ans=INT_MAX;for(int i=0;i<=k;i++)ans=min(ans,l[t][i]);return ans;
}
int main(){cin>>n>>m>>k;cin>>s>>t;while(m--){int u,v,w;cin>>u>>v>>w;G[u].push_back({u,v,w});G[v].push_back({v,u,w});}cout<<Dijkstra(s,t);return 0;
}

0x02 负环

在讲单元最短路时讲过在求最短路时不能出现负环

那我们样如何判断负环呢

首先我们要知道一条最短路径一定是一条链(废话

那链的长度不会超过 $V-1$ 条边

所以我们可以在做 SPFA 时记录从 $s$ 到 $i$ 的最短路径上有几条边记作 $cnt_i$ 如果有负环那 $cnt_i$ 会一直增加最后超过 $n-1$ 这样就可以判断负环了

为什么用 SPFA


这时有人会问了SPFA不死了吗? 干嘛用它啊?那我们看看其他算法是否可以1. Dijkstra 这个不能在负权图上 淘汰
2. Floyd $\mathcal{O}(n^3) $ 不如 SPFA 淘汰
3. Bellman-Ford SPFA是它的优化 不如 SPFA 淘汰好吧 看来SPFA是最好的了

code:

//LG
//【模板】负环
//https://www.luogu.com.cn/problem/P3385
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct e{int u,v,w;
};
vector<e> G[2010];
int n,m,T;
ll SPFA(){vector<int> l(n+10,INT_MAX);l[1]=0;vector<int> cnt(n+10,0);vector<bool> f(n+10,1);f[1]=0;queue<int> q;q.push(1);while(q.size()){int u=q.front();q.pop();f[u]=1;for(int i=0;i<G[u].size();i++){int v=G[u][i].v,w=G[u][i].w;if(l[v]>l[u]+w){cnt[v]=cnt[u]+1;l[v]=l[u]+w;if(f[v]){q.push(v);f[v]=0;}}if(cnt[v]>=n)return 0;}}return 1;
}
int main(){cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++)G[i].clear();while(m--){int u,v,w;cin>>u>>v>>w;if(w>=0){G[u].push_back({u,v,w});G[v].push_back({v,u,w});}else{G[u].push_back({u,v,w});}}cout<<(SPFA()?"NO\n":"YES\n");}return 0;
}

0x03 差分约束

这是有人问了(没有

判断有没有负环有啥用啊

它有个十分强大的用处就是解像这样的不等式

\[\left\{\begin{matrix} x_{c_1}-x_{c_1'} \le y_1 \\ x_{c_2}-x_{c_2'} \le y_2 \\ x_{c_3}-x_{c_3'} \le y_3 \\\vdots \\ x_{c_n}-x_{c_n'} \le y_n \\ \end{matrix}\right. \]

这和最短路有啥关系啊?

其实它的每一条都很想松弛的条件你看 $x_{c_i}\le y_i+x_{c_i'} $ 和 $l_v \le l_u + (u,v)$

所以说我们可以设计一条 $x_{c_i'}$ 到 $x_{c_i}$ 的一条边权为 $y_i$ 的边然后跑一次 SPFA 如果有负环就无解否则 $l$ 就是解

查看全文

http://www.jsqmd.com/news/591891/