0%

分层图最短路

分层图最短路

在最短路中涉及策略时,将图建为多层,用层间边作为选择。
即,扩展图,对k次决策,建(k+1)层,即每个节点扩展为k+1个。
层间有单向边,如果每次决策的顺序没有影响,就跑一次,否则枚举决策的顺序。

用两个例子说明:

cf 1473e:Minimum Path

题意是无向图最短路,对每条路删去最大权,将最小权*2,求这种情况下的最短路。

  • 两次决策,建三层
  • 两个层间,建权为0和2*z的
  • 对每个原有的边,每层中建双向边,层间从上向下建单向边
  • 0和2*z谁先不定,建两个图
  • vis 中,每个点在所有层中只能被访问一次
  • 如果最短路没有层数长,也要考虑,即对每层的dis[t]求最小值(如果有此情况,最后一层dis[t]是inf)

所以建两层,做两次。

luogu P4568: 飞行路线

同样,建k+1层,层间权为0
可以不需要k次,即对每层的dis求最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10,M=7e4+10;
int n,m,k,tot,s,t,a,b,c;
int dis[11*N];
int vis[11*N];
int ver[45*M],edge[45*M],nxt[45*M];
int head[11*N];
void add(int x,int y,int z){
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
edge[tot]=z;
}
void dij(int s){
memset(vis,0,sizeof vis);
dis[s]=0;priority_queue<pair<int ,int> >q;
q.push(make_pair(0,s));
while(q.size()){
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
int z=edge[i];
if(dis[y]>dis[x]+z){
dis[y]=dis[x]+z;
q.push(
make_pair(-dis[y],y)
//存进去只是排序 而已
);
}
}
}
}
int main()
{
memset(dis,0x3f,sizeof dis);
tot=0;
cin>>n>>m>>k;
cin>>s>>t;
for(int i=1;i<=m;++i){
cin>>a>>b>>c;
add(a,b,c);add(b,a,c);
for(int i=1;i<=k;++i){
add(a+i*n,b+i*n,c);
add(b+i*n,a+i*n,c);
add(a+(i-1)*n,b+i*n,0);
add(b+(i-1)*n,a+i*n,0);
}
}
dij(s);
int mi=dis[t];
for(int i=1;i<=k;++i){
mi=min(mi,dis[i*n+t]);
}
cout<<mi<<endl;
}

总结

要注意这几个点:

  • k次决策,k+1层
  • 最短路可能比k短
  • 顺序要考虑
  • 注意数组大小,k+1层这样的图,有$(k+1)\times 2 \times m+m\times 2\times k=(4k+2)m$个边,节点个数则为$(k+1)\times n$。
  • 如果涉及多张图,边可以建在一起,但head要分开,dis要分开。