浅析分层图最短路
分层图最短路
1.适用场景
题目对边的权值提供可选的操作，比如可以将一定数量的边权减半，在此基础上求解最短路。
2.算法思路
根据是否进行题目提供的操作以及操作次数的不同，会产生非常多的情况，如果考虑何时使用操作，情况更多。如果将在图上求解最短路看成是在二维平面上进行的，引入进行操作的次数 k 做为第三维，那么这个三维空间就理应可以包含所有的情况，便可以在这个三维空间上解决问题。
每进行一次操作（k+1），除了操作的边，其他边没有任何变化，在 k=0,1,2,…，时图都是一样的，那么就将图复制成 k+1 份，第 i 层图代表进行了 i 次操作后的图。
每相邻两层图之间的联系，应该决定了一次操作是发生在哪条边上。根据操作的特点可以 i 层点到 i+1 层点的边来表示一次操作。
那么对于分层图的构建步骤可以描述为： 1、先将图复制成 k+1 份 （0 ~k） 2、对于图中的每一条边 <u,v> 从 ui 到 vi+1 建立与题目所给操作相对应的边（i=0,1,…,k）
其中k代表了进行操作的次数，而每层之间点的关系代表了何时进行操作。
3.基本模板（可能有点丑
最短路部分还是和普通的最短路模板一样，唯一的区别是初始化时要初始化整个三维空间，共k+1层图，这里贴一下我Dijkstra的模板。为了方便理解，我用的是结构体+重载运算符实现小根堆，一般是用pair。
struct node
{
int w,now;
const bool operator < (const node &x) const
{
return w>x.w;
}
};
priority_queue <node> q;
inline void add(int u,int v,int w)//链式前向星存图
{
edge[++num_edge].nxt=head[u];
edge[num_edge].dis=w;
edge[num_edge].to=v;
head[u]=num_edge;
}
void dij()
{
for(RE int i=1;i<=k*n+n;i++)//注意分层图的初始化不是n,而是k*n+n！！！
dis[i]=INF;
q.push( (node) {0,s});//s表示起始点
dis[s]=0;
while(!q.empty())
{
node x=q.top();
q.pop();
int u=x.now;
if(vis[u])
continue;
vis[u]=1;
for(RE int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
q.push( (node) {dis[v],v});
}
}
}
}
在存图部分，稍微较普通最短路麻烦一点，因为有向图要存1+2k条边，而无向图要再翻一倍。
for(RE int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w);// add(v,u,w);
for(RE int j=1;j<=k;j++)
add(u+n*(j-1),v+n*j,A),
add(u+j*n,v+j*n,w)/*,
add(v+n*(j-1),u+n*j,A),
add(v+j*n,u+j*n,w)*/;
}//这里的A代表题目中要求的操作，如减半、变成0等。4.几道例题（代码也很丑
P4822 [BJWC2012]冻结
典型分层图，操作是减半。代码如下：
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIEI std::cin.tie(nullptr)
#define TIEO std::cout.tie(nullptr)
#define INF 0x7fffffff
#define RE register
#define pii pair<int,int>
#define kp make_pair
#define fi first
#define se second
#define IT iterator
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 Int;
const int N=50+10;
const int M=1e3+10;
const LL MOD=1e8-3;
LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+(LL)(ch-'0'),ch=getchar();
return x*f;
}
void write(LL n)
{
if(n<0)
putchar('-'),
n=-n;
if(n>=10)
write(n/10);
putchar(n%10+'0');
}
void writes(LL n)
{
write(n);putchar(' ');
}
void writee(LL n)
{
write(n);puts("");
}
LL n,m,k,num_edge,ans=INF;
LL head[M*210],dis[N*210],vis[N*210];
struct Edge
{
int nxt,dis,to;
bool k;
}edge[M*210];
struct node
{
int w,now;
const bool operator < (const node &x) const
{
return w>x.w;
}
};
priority_queue <node> q;
inline void add(int u,int v,int w)
{
edge[++num_edge].nxt=head[u];
edge[num_edge].dis=w;
edge[num_edge].to=v;
head[u]=num_edge;
}
void dij()
{
for(RE int i=1;i<=n*k+n;i++)
dis[i]=INF;
q.push( (node) {0,1});
dis[1]=0;
while(!q.empty())
{
node x=q.top();
q.pop();
int u=x.now;
if(vis[u])
continue;
vis[u]=1;
for(RE int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
q.push( (node) {dis[v],v});
}
}
}
}
int main()
{
n=read(),m=read(),k=read();
for(RE int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
for(RE int j=0;j<=k;j++)
add(j*n+u,j*n+v,w),add(j*n+v,j*n+u,w);
for(RE int j=0;j<k;j++)
add(j*n+u,(j+1)*n+v,w/2),add(j*n+v,(j+1)*n+u,w/2);
}
dij();
for(RE int i=0;i<=k;i++)
ans=min(ans,dis[i*n+n]);
write(ans);
return 0;
}P4568 [JLOI2011] 飞行路线
依旧很典型，操作是将权值变成0。代码如下：
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIEI std::cin.tie(nullptr)
#define TIEO std::cout.tie(nullptr)
#define INF 0x7fffffff
#define RE register
#define pii pair<int,int>
#define kp make_pair
#define fi first
#define se second
#define IT iterator
#define pb push_back
#define Ls(a) a<<1
#define Rs(a) a<<1|1
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef __int128 Int;
const int N=120000+10;
const int M=2500000+10;
const LL MOD=1000007;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+(LL)(ch-'0'),ch=getchar();
return x*f;
}
void write(LL n)
{
if(n<0)
putchar('-'),
n=-n;
if(n>=10)
write(n/10);
putchar(n%10+'0');
}
void writes(LL n)
{
write(n);putchar(' ');
}
void writee(LL n)
{
write(n);puts("");
}
int n,m,k,s,t,num_edge,ans=INF;
int head[N],dis[N],vis[N];
struct Edge
{
int nxt,dis,to;
}edge[M];
struct node
{
int w,now;
const bool operator < (const node &x) const
{
return w>x.w;
}
};
priority_queue <node> q;
inline void add(int u,int v,int w)
{
edge[++num_edge].nxt=head[u];
edge[num_edge].dis=w;
edge[num_edge].to=v;
head[u]=num_edge;
}
void dij()
{
for(RE int i=0;i<=k*n+n;i++)
dis[i]=INF;
q.push( (node) {0,s});
dis[s]=0;
while(!q.empty())
{
node x=q.top();
q.pop();
int u=x.now;
if(vis[u])
continue;
vis[u]=1;
for(RE int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis)
{
dis[v]=dis[u]+edge[i].dis;
q.push( (node) {dis[v],v});
}
}
}
}
int main()
{
n=read();m=read();k=read();
s=read();t=read();
for(RE int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
add(u,v,w); add(v,u,w);
for(RE int j=1;j<=k;j++)
add(u+(j-1)*n,v+j*n,0),
add(v+(j-1)*n,u+j*n,0),
add(u+j*n,v+j*n,w),
add(v+j*n,u+j*n,w);
}
dij();
for(RE int i=0;i<=k;i++)
ans=min(ans,dis[t+i*n]);
write(ans);
return 0;
}（逃