分层图最短路是指在可以进行分层图的图上解决最短路问题。分层图：可以理解为有多个平行的图。
图片来源
这个图的意思是第0层是原始的图，上面的1—k层都是第0层的映射。
- 层内(同一层)，仍然是u->v的关系，权值为w.
- 层间(不同层），也是u->v的关系，但权值是0,
- 比如图中的
与
是同一层距离为3，
是不同层距离为0。这就是分层操作。
所以开数组的时候要格外注意，以为有k+1层，那么就n*(k+1)个点，那么就有(2k+1)*m条边。
飞行路线
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=5000500;
int head[M],cnt;
struct node
{
int v,w;
int nxt;
}edge[M];
int n,m,k,s,t,x,y,w;
int dis[M],vis[M];
void add(int x,int y,int w)
{
edge[++cnt].nxt=head[x];
edge[cnt].v=y;
edge[cnt].w=w;
head[x]=cnt;
}
void Dijkstra(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
//vis[x]=1;
dis[x]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qu;//first是dis[v]的最小距离，second是当前点的id,优先队列的优先级先考虑pair.first
qu.push(make_pair(0,x));
while(!qu.empty( ))
{
int u=qu.top( ).second;
qu.pop( );
if(!vis[u])
{
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].nxt)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
qu.push(make_pair(dis[v],v));
}
}
}
}
}
int main( )
{
cin>>n>>m>>k>>s>>t;
s++,t++;
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
cin>>x>>y>>w;
x++,y++;
for(int j=0;j<=k;j++)
{
add(x+j*n,y+j*n,w);//相同层，距离为w
add(y+j*n,x+j*n,w);
}
for(int j=1;j<=k;j++)
{
add(x+n*(j-1),y+n*j,0);//上下层边，距离为0
add(y+n*(j-1),x+n*j,0);
}
}
for(int i=1;i<=k;i++)
{
add(t+(i-1)*n,t+i*n,0);//连接各层的t
}
Dijkstra(s);
cout<<dis[t+k*n]<<endl;//输出最高层的t就是答案
return 0;
}
dp思想
想象将一个点拆分为k + 1个点，分别表示到这个点时，免费权消耗了0次，1次，2次......k次
这样实际我们可以把这k个点想象成对应dp的不同的状态
- dis[i][j]表示到第i个点时，消耗了j次乘车权后的最短路线
- vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.
我们用to表示要到达的点，x表示父亲节点，就有
dis[to][j] = min(dis[x][j] + val(x, to), dis[x][j - 1])
因为我们跑最短路时是从前向后跑，也就是当前状态推出后继状态，所以实际上我们可以推出两个可能状态
如果我们消耗了免费过路权(前提是还有免费的过路权）
dis[to][j] = min{dis[x][j - 1]}
如果我们没消耗免费过路权
dis[to][j] = min{dis[x][j] + val(x, to)}
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=1e5+10;
int dis[M][15];
int vis[M][15];
int head[M],cnt;
int n,m,k,s,t;
struct node
{
int v;
int w;
int nxt;
} edge[M<<4];
void add(int x,int y,int w)
{
edge[++cnt].nxt=head[x];
edge[cnt].v=y;
edge[cnt].w=w;
head[x]=cnt;
}
void Dijkstra(int x)
{
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
dis[x][0]=0;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qu;
qu.push(make_pair(0,x));
while(!qu.empty( ))
{
int u=qu.top( ).second;
qu.pop( );
int tt=u/n;//求出已经使用了多少次免费的路权，相当于分层思想中处在多少层
u%=n;//当前的节点
if(vis[u][tt]==1)
{
continue;
}
vis[u][tt]=1;
for(int i=head[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
if(!vis[v][tt]&&dis[v][tt]>dis[u][tt]+edge[i].w)
{
dis[v][tt]=dis[u][tt]+edge[i].w;
qu.push(make_pair(dis[v][tt],v+tt*n));//v+tt*n相当于分层思想中的同一层，于是要加边长w
}
}
if(tt<k)
{
for(int i=head[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
if(!vis[v][tt+1]&&dis[v][tt+1]>dis[u][tt])
{
dis[v][tt+1]=dis[u][tt];
qu.push(make_pair(dis[v][tt+1],(tt+1)*n+v));//v+(tt+1)*n相当于分层中的不同层，边长w=0
}
}
}
}
}
int main( )
{
cin>>n>>m>>k>>s>>t;
cnt=0;
int x,y,w;
memset(head,-1,sizeof(head));
for(int i=0; i<m; i++)
{
cin>>x>>y>>w;
add(x,y,w);
add(y,x,w);
}
Dijkstra(s);
int ans=INF;
for(int i=0; i<=k; i++)
{
ans=min(ans,dis[t][i]);
}
cout<<ans<<endl;
return 0;
}
网友评论