0. 0. 0.写在前面
最短路算法一般在算法竞赛中有四种比较常见,
F
l
o
y
d
Floyd
Floyd算法,
B
e
l
l
m
a
n
−
F
o
r
d
Bellman-Ford
Bellman−Ford算法,
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法,
S
P
F
A
SPFA
SPFA算法。
F
l
o
y
d
Floyd
Floyd算法和
B
e
l
l
m
a
n
−
F
o
r
d
Bellman-Ford
Bellman−Ford算法的时间复杂度分别为
O
(
n
3
)
O(n^3)
O(n3)和
O
(
n
m
)
O(nm)
O(nm)。
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2),用堆优化之后的复杂度可以稳定在
O
(
n
log
n
)
O(n\log n)
O(nlogn),是目前使用最多的最短路算法,在各大网络地图中都有应用。缺点是不能求单点对单点的最短路,只能将单点到所有点的最短路求出,而且仅适用于有向加权图,无法处理边为负值的图。
S
P
F
A
SPFA
SPFA算法的本质是
B
e
l
l
m
a
n
−
F
o
r
d
Bellman-Ford
Bellman−Ford算法的改良版本,但其实更像一种贪心算法,时间复杂度为
O
(
k
m
)
O(km)
O(km),但会被卡到
O
(
n
m
)
O(nm)
O(nm),有几种优化可以解决部分情况,具体看我早年的一篇博客SPFA的几种优化以及Hack的方法,不过就是再好的优化也会被卡,所以大部分题建议无脑
d
i
j
k
+
dijk+
dijk+堆优化。
1. 1. 1.例题
P3371 【模板】单源最短路径(弱化版)
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:用
d
i
j
k
s
t
r
a
dijkstra
dijkstra算法求出单点到所有点的最短路即可,由于
n
<
=
1
e
4
n<=1e4
n<=1e4,不需要堆优化。
#include<bits/stdc++.h>
#define N 10010
#define M 500050
#define reg register
using namespace std;
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int to,nxt,val;
}edge[M<<1];
int n,m,s,u,v,w,cnt,head[N],dis[N],vis[N];
inline void addedge(int u, int v, int w){
edge[++cnt].to=v,edge[cnt].nxt=head[u],edge[cnt].val=w,head[u]=cnt;
}
inline void superadd(int u, int v, int w){
addedge(u,v,w),addedge(v,u,w);
}
void dijkstra(){
memset(dis,0x3f3f3f3f,sizeof dis);
dis[s]=0;
int x=s;
while(x){
x=0;
for(int i=1;i<=n;i++)if(dis[i]<dis[x]&&!vis[i])x=i;
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt){
int v=edge[i].to;
dis[v]=min(dis[v],dis[x]+edge[i].val);
}
}
}
int main(){
read(n),read(m),read(s);
for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
dijkstra();
for(reg int i=1;i<=n;i++){
if(dis[i]==dis[0])printf("2147483647 ");
else printf("%d ",dis[i]);
}
putchar('\n');
}
P4779 【模板】单源最短路径(标准版)
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:由于边的数量超过了
1
e
5
1e5
1e5,所以
O
(
n
2
)
O(n^2)
O(n2)的算法是过不了,我们选择堆优化的
d
i
j
k
s
t
r
a
dijkstra
dijkstra算法进行求解。
#include<bits/stdc++.h>
#define N 100100
#define M 500050
#define reg register
using namespace std;
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int to,nxt,val;
}edge[M<<1];
struct pnt{
int d,p;
bool operator <(const pnt &x) const{
return x.d<d;
}
};
priority_queue<pnt> q;
int n,m,s,u,v,w,cnt,head[N],dis[N],vis[N];
inline void addedge(int u, int v, int w){
edge[++cnt].to=v,edge[cnt].nxt=head[u],edge[cnt].val=w,head[u]=cnt;
}
inline void superadd(int u, int v, int w){
addedge(u,v,w),addedge(v,u,w);
}
void dijkstra(){
memset(dis,0x3f3f3f3f,sizeof dis);
dis[s]=0;
pnt x;x.d=0,x.p=s;q.push(x);
while(!q.empty()){
x=q.top();q.pop();
if(vis[x.p])continue;
vis[x.p]=1;
for(int i=head[x.p];i;i=edge[i].nxt){
int v=edge[i].to;
dis[v]=min(dis[v],dis[x.p]+edge[i].val);
if(!vis[v]){
pnt y;y.d=dis[v],y.p=v;
q.push(y);
}
}
}
}
int main(){
read(n),read(m),read(s);
for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
dijkstra();
for(reg int i=1;i<=n;i++){
if(dis[i]==dis[0])printf("2147483647 ");
else printf("%d ",dis[i]);
}
putchar('\n');
}
P5905 【模板】Johnson 全源最短路
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:本题要求每个点到所有点的最短路径,并且带有负边权,如果在没有负边权的情况下可以用
n
n
n次堆优化的
d
i
j
k
s
t
r
a
dijkstra
dijkstra算法在
O
(
n
2
l
o
g
n
)
O(n^2log_n)
O(n2logn)的时间计算出答案,但是这题有负边权,所以现在应考虑如何处理负边权。
首先考虑将所有加上一个较大的值,那么将不保证正确性,比如从
a
a
a到
b
b
b,一条路是
a
−
>
c
1
−
>
b
a->c_1->b
a−>c1−>b,一条路是
a
−
>
c
1
−
>
c
2
−
>
b
a->c_1->c_2->b
a−>c1−>c2−>b,假设边权都为
−
1
-1
−1,显然第二条路是最短路,但将每个边都加上一个较大的值后第一条路就变为最短路了。
这里介绍
J
o
h
n
s
o
n
Johnson
Johnson算法处理负边权,我们新建一个
0
0
0结点,并将其向所有点连一条边权为
0
0
0的一条边,接着用
B
e
l
l
m
a
n
−
F
o
r
d
Bellman-Ford
Bellman−Ford算法求解
0
0
0到所有边的最短路,记为
d
i
d_i
di,假如存在一条从
u
u
u到
v
v
v边权为
w
w
w的边,我们将其边权修改为
w
+
d
u
−
d
v
w+d_u-d_v
w+du−dv,这样所有边权就被修改为非负的,且不会影响正确性。
如何理解
J
o
h
n
s
o
n
Johnson
Johnson算法呢,我们可以将
d
i
d_i
di理解为以
0
0
0结点为零势能点的势能大小,无论从
u
u
u到
v
v
v走什么样的路径,
d
u
−
d
v
d_u-d_v
du−dv是一个定值。其次如何证明修改操作过后的所有边为非负的呢,由于
d
u
,
d
v
d_u,d_v
du,dv是从
0
0
0结点到
u
,
v
u,v
u,v结点的最短路,故从
0
0
0到
u
u
u再到
v
v
v的路径一定大于等于
d
v
d_v
dv,即
d
v
≤
d
u
+
w
d_v\leq d_u+w
dv≤du+w因此
w
+
d
u
−
d
v
≥
0
w+d_u-d_v\geq0
w+du−dv≥0,故所有边权为非负,此时再用
n
n
n次
d
i
j
k
s
t
r
a
dijkstra
dijkstra算法进行求解即可。
注意本题可能有负环,应先用
s
p
f
a
spfa
spfa判一遍负环,再进行求解,可以直接用
s
p
f
a
spfa
spfa更新
d
d
d数组,顺便进行判负环操作。
#include<bits/stdc++.h>
#define N 3030
#define M 6060
#define reg register
using namespace std;
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int to,val,nxt;
}edge[M<<1];
struct pnt{
int dis,pos;
bool operator <(const pnt &x) const{
return x.dis<dis;
}
};
int n,m,s,u,v,w,cnt,head[N],tot[N],vis[N],dis[N],f[N];
inline void addedge(int u, int v, int w){
edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt,edge[cnt].val=w;
}
inline void superadd(int u, int v, int w){
addedge(u,v,w),addedge(v,u,w);
}
bool spfa(int s){
queue<int> q;
memset(vis,0,sizeof vis);
memset(f,0x3f,sizeof f);
f[s]=0,vis[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();vis[u]=false;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(f[v]>f[u]+edge[i].val){
f[v]=f[u]+edge[i].val;
if(!vis[v]){
vis[v]=true,tot[v]++;q.push(v);
if(tot[v]>n)return false;
}
}
}
}
return true;
}
void dijkstra(int s){
memset(dis,0x7f,sizeof dis);
memset(vis,0,sizeof vis);
priority_queue<pnt> q;
dis[s]=0;
pnt x;x.dis=0,x.pos=s;q.push(x);
while(!q.empty()){
x=q.top();q.pop();
if(vis[x.pos])continue;
vis[x.pos]=true;
for(reg int i=head[x.pos];i;i=edge[i].nxt){
int v=edge[i].to;
if(dis[v]>dis[x.pos]+edge[i].val){
dis[v]=dis[x.pos]+edge[i].val;
if(!vis[v]){
pnt y;y.dis=dis[v],y.pos=v;
q.push(y);
}
}
}
}
return ;
}
int main(){
read(n),read(m);
for(reg int i=1;i<=m;i++)read(u),read(v),read(w),addedge(u,v,w);
for(reg int i=1;i<=n;i++)addedge(0,i,0);
if(!spfa(0)){
puts("-1");return 0;
}
for(int u=1;u<=n;u++){
for(int j=head[u];j;j=edge[j].nxt){
int v=edge[j].to;
edge[j].val+=f[u]-f[v];
}
}
for(int i=1;i<=n;i++){
dijkstra(i);
long long ans=0;
for(int j=1;j<=n;j++){
if(dis[j]==dis[n+1])ans+=j*(long long)(1e9);
else ans+=j*(long long)(dis[j]+f[j]-f[i]);
}
cout<<ans<<endl;
}
}
P1144 最短路计数
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:本题要求无向无权图中单点到所有点最短路的数目,我们将无权图每条边的边权默认为1,则起点到某一点的最短路即为从起点开始
b
f
s
bfs
bfs,遍历到该点的深度。我们考虑求最短路的过程,即更新
d
i
s
dis
dis数组的过程,当
d
i
s
[
v
]
>
d
i
s
[
u
]
+
v
a
l
u
e
dis[v]>dis[u]+value
dis[v]>dis[u]+value时,取
d
i
s
[
v
]
=
d
i
s
[
u
]
+
v
a
l
u
e
dis[v]=dis[u]+value
dis[v]=dis[u]+value,若设题中所求起点到点
i
i
i的最短路的数目为
a
n
s
[
i
]
ans[i]
ans[i],则此时应同时取
a
n
s
[
v
]
=
a
n
s
[
u
]
ans[v]=ans[u]
ans[v]=ans[u]。显然这样所有可到达的点
a
n
s
ans
ans值都会为
1
1
1,因为每个点只会被第一次更新
d
i
s
dis
dis数组的点更新
a
n
s
ans
ans数组,所以我们应多进行一次对于
a
n
s
ans
ans数组的更新,当
d
i
s
[
v
]
=
d
i
s
[
u
]
+
v
a
l
u
e
dis[v]=dis[u]+value
dis[v]=dis[u]+value时,我们应同时更新
a
n
s
[
v
]
+
=
a
n
s
[
u
]
ans[v]+=ans[u]
ans[v]+=ans[u]。即可在更新最短路的同时更新最短路计数。由于
N
N
N和
M
M
M是在
1
0
6
10^6
106级别的,所以使用堆优化的
D
i
j
k
s
t
r
a
Dijkstra
Dijkstra算法进行最短路求解,这种大数据
S
P
F
A
SPFA
SPFA可能会被出题人构造的特殊数据卡掉,但是看题解里应该
S
P
F
A
SPFA
SPFA应该没被卡,有感兴趣的可以自己写写。
#include<bits/stdc++.h>
#define N int(1e6+100)
#define M int(2e6+100)
#define reg register
using namespace std;
const int mod=100003;
struct node{
int to,nxt;
}edge[M<<1];
struct pnt{
int d,id;
pnt(int b, int a){d=a,id=b;}
bool operator >(const pnt &x) const{
return x.d>d;
}
bool operator <(const pnt &x) const{
return x.d<d;
}
};
int head[N],cnt,n,m,u,v,ans[N],dis[N],vis[N];
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
inline void addedge(int u, int v){
edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt;
}
inline void superadd(int u, int v){
addedge(u,v),addedge(v,u);
}
void dijkstra(){
memset(dis,0x3f3f3f3f,sizeof dis);
priority_queue<pnt> q;
dis[1]=0;q.push(pnt(1,0));
ans[1]=1;
while(!q.empty()){
pnt x=q.top();q.pop();
if(vis[x.id])continue;
vis[x.id]=1;
for(reg int i=head[x.id];i;i=edge[i].nxt){
int v=edge[i].to;
if(dis[v]>1+dis[x.id])dis[v]=dis[x.id]+1,ans[v]=ans[x.id];
else if(dis[v]==1+dis[x.id])(ans[v]+=ans[x.id])%=mod;
if(!vis[v])q.push(pnt(v,dis[v]));
}
}
return ;
}
int main(){
read(n),read(m);
for(reg int i=1;i<=m;i++)read(u),read(v),superadd(u,v);
dijkstra();
for(reg int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
P1462 通往奥格瑞玛的道路
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:题里说每通过一条道路会扣一个血量,每通过一个城市会扣除费用,那么我们可以把血量看作边权,费用看作点权。题目中求所经过的城市的最大收费最小,很容易想到二分,通过二分法限制城市的最大收费,如果求最短路的过程中碰到一个城市的收费超过了我们所限制的最大收费,则不更新该点,否则正常更新,最后判断如果
d
i
s
[
n
]
dis[n]
dis[n]不超过初始血量值,则证明该最大收费可行,继续进行二分法。
初始时我们先空走一遍最短路,如果不能到达
n
n
n那么输出
A
F
K
AFK
AFK,然后通过二分答案求得经过城市最大收费的最小值。
注意:
1.
1.
1.判断能否到达
n
n
n不是判断是否联通,是判断到
n
n
n的最短路是否小于所给初值
2.
2.
2.题中边权最大为
1
0
9
10^9
109,用
m
e
m
s
e
t
memset
memset初始化
d
i
s
dis
dis数组时应注意不要使用
0
x
7
f
0x7f
0x7f,会导致爆
i
n
t
int
int。
#include<bits/stdc++.h>
#define reg register
#define N 10010
#define M 50020
using namespace std;
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int to,val,nxt;
}edge[M<<1];
struct pnt{
int id,d;
pnt(int x, int y){
id=x,d=y;
}
bool operator <(const pnt &x) const {
return x.d<d;
}
};
int head[N],n,m,cnt,b,vis[N],dis[N],f[N],u,v,w;
inline void addedge(int u, int v, int w){
edge[++cnt].to=v,edge[cnt].nxt=head[u],head[u]=cnt,edge[cnt].val=w;
}
inline void superadd(int u, int v, int w){
addedge(u,v,w),addedge(v,u,w);
}
bool dijkstra(int fe){
if(fe<f[1])return false;
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
priority_queue<pnt> q;
dis[1]=0;q.push(pnt(1,0));
while(!q.empty()){
pnt now=q.top();q.pop();
if(vis[now.id])continue;
vis[now.id]=1;
for(int i=head[now.id];i;i=edge[i].nxt){
int vv=edge[i].to;
if(f[vv]<=fe){
dis[vv]=min(dis[vv],dis[now.id]+edge[i].val);
if(!vis[vv])q.push(pnt(vv,dis[vv]));
}
}
}
return dis[n]<=b;
}
int main(){
read(n),read(m),read(b);
for(reg int i=1;i<=n;i++)read(f[i]);
for(reg int i=1;i<=m;i++)read(u),read(v),read(w),superadd(u,v,w);
int l=1,r=1e9+1,mid=0,ans;
if(!dijkstra(r)){puts("AFK");return 0;}
while(l<=r){
mid=l+r>>1;
if(dijkstra(mid))r=mid-1,ans=mid;
else l=mid+1,ans=l;
}
cout<<ans<<endl;
}
先发吧,发出来也能更好督促自己更新
U P D 0618 UPD0618 UPD0618文章来源:https://www.toymoban.com/news/detail-483657.html
P1522 [USACO2.4] 牛的旅行 Cow Tours
题面
S
o
l
u
t
i
o
n
:
Solution:
Solution:题目大意就是一个非连通图,要求在两个不同的连通分量中选两个点加一条边,最后使得图的任意两点之间的最短路中最大的那个最小。
看到
n
n
n为
150
150
150,考虑直接暴力,因为要求所有点之间的最短路,所以选用
f
l
o
y
d
floyd
floyd算法进行求解每个联通块中任意两点的最短路,并预处理出该连通块中最大的最短路。每次枚举两个不同连通块的点,设其为
p
1
,
p
2
p_1,p_2
p1,p2,两个连通块只有
p
1
,
p
2
p_1,p_2
p1,p2这一条边相连,因此两个连通块合并后
p
1
,
p
2
p_1,p_2
p1,p2所在连通块的最大最短路分别为
d
i
s
1
m
a
x
,
d
i
s
2
m
a
x
dis1_{max},dis2_{max}
dis1max,dis2max,
p
1
,
p
2
p_1,p_2
p1,p2在其所在连通块中距离最远的点为
p
x
,
p
y
p_x,p_y
px,py则最终答案
a
n
s
=
m
i
n
{
a
n
s
,
m
a
x
{
d
i
s
1
m
a
x
,
d
i
s
2
m
a
x
,
d
i
s
(
p
1
,
p
2
)
+
d
i
s
(
p
x
,
p
1
)
+
d
i
s
(
p
y
,
p
2
)
}
}
ans=min\{ans,max\{dis1_{max},dis2_{max},dis(p_1,p_2)+dis(p_x,p_1)+dis(p_y,p_2)\}\}
ans=min{ans,max{dis1max,dis2max,dis(p1,p2)+dis(px,p1)+dis(py,p2)}}文章来源地址https://www.toymoban.com/news/detail-483657.html
#include<bits/stdc++.h>
#define N 200
#define reg register
using namespace std;
inline void read(int &x){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch&15);ch=getchar();}
x=s*w;
}
struct node{
int x,y;
}p[N];
double di5(node a, node b){
return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
int n,fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x, int y){
x=find(x),y=find(y);
if(x==y)return ;
fa[y]=x;
}
double sqr[N][N],dis[N][N],mdis[N],sdis[N],ans=1e9;
char chr;
int main(){
read(n);
for(reg int i=1;i<=n;i++)read(p[i].x),read(p[i].y),fa[i]=i;
for(reg int i=1;i<=n;i++){
for(reg int j=1;j<=n;j++){
chr=getchar();
while(chr!='0'&&chr!='1')chr=getchar();
if(chr=='1')sqr[i][j]=sqr[j][i]=di5(p[i],p[j]),merge(i,j);
}
}
for(reg int i=1;i<=n;i++){
for(reg int j=1;j<=n;j++){
if(sqr[i][j])dis[i][j]=sqr[i][j];
else dis[i][j]=1e9;
if(i==j)dis[i][j]=0;
}
}
for(reg int k=1;k<=n;k++){
for(reg int i=1;i<=n;i++){
for(reg int j=1;j<=n;j++){
dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
}
}
}
for(reg int i=1;i<=n;i++){
for(reg int j=1;j<=n;j++){
if(find(i)==find(j))mdis[i]=max(mdis[i],dis[i][j]),sdis[find(i)]=max(sdis[find(i)],dis[i][j]);
}
}
for(reg int i=1;i<=n;i++){
for(reg int j=1;j<=n;j++){
if(find(i)!=find(j)){
ans=min(ans,max(max(mdis[i]+mdis[j]+di5(p[i],p[j]),sdis[find(i)]),sdis[find(j)]));
}
}
}
printf("%.6lf\n",ans);
}
到了这里,关于洛谷题单 Part 8.2 最短路问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!