分层图(图解+例题)

分层图

分层图多用于求最短路径,但是最短路径中可以有k条边的权值为0。

既然可以k条边为0,那么对于k条边的选取就是个问题。
所以有了分层图的概念。

对于每个点都可以选择下一条边是否赋予权值为0,那么我们就可以将图画出k+1层。

图例

我们简单画一下一个有向图,并且k=1(有一条边权值可以为0)

在这里插入图片描述
(这是初始情况,接下来我们分层)
k=1,我们要分k+1层

我们模拟从0开始,0可以走的路路径
在这里插入图片描述

我们可以看到,如果走同一层,那么权值就要+5或这+100,如果向上一层走那么要加上权值0,并且k减减,也就是每次移动可以消耗免费次数和不消耗免费次数这两种情况可以选择!

那么剩下的情况大家可以手动画一下。

代码实现

我们可以将dis数组开成二维dis[i][j]表示到达i号结点,用了j次免费操作!
比如dis[2][0]表示到达2号结点,没有用免费操作,也就是在第一层图移动。
比如dis[2][3],到达2号结点用了3次免费操作,那么下一次移动应该在第3/4层图进行!

注意理解上述操作!

接下来是一道例题,大家可以动手完成。(我用的是dijkstra+优先队列优化,完成k次免费的最短路径问题)

飞行路线

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e4+10;
int dis[maxn][15],vis[maxn][15],head[maxn];
int n,m,k,sum;
int start,last;
struct node
{
    int id,v,used;//used使用了几次免费券
    node() {}
    node(int id,int v,int used):id(id),v(v),used(used) {}
    bool  operator <(const node b) const
    {
        return v>b.v;
    }
};
//链式前向星构图
struct edge
{
    int to,next,w;
} edge[maxn<<1];

void add(int u,int v,int w)
{
    edge[++sum].to=v;
    edge[sum].next=head[u];
    edge[sum].w=w;
    head[u]=sum;
}

void dijkstra(int start)
{
    memset(dis,0x7f7f7f7f,sizeof(dis));
    priority_queue<node> q;
    q.push(node(start,0,0));
    dis[start][0]=0;
    while(!q.empty())
    {
        node t=q.top();
        q.pop();
        int u=t.id;
        int kk=t.used;
        if(vis[u][kk])continue;
        vis[u][kk]=1;
        for(int i=head[u]; i; i=edge[i].next)
        {
            int v=edge[i].to;
            int w=edge[i].w;
            //两种情况,用免费和不用免费
            //不用
            if(dis[v][kk]>dis[u][kk]+w)
            {
                dis[v][kk]=dis[u][kk]+w;
                q.push(node(v,dis[v][kk],kk));
            }
            //用免费券
            if(kk+1<=k&&dis[v][kk+1]>dis[u][kk]+0)
            {
                dis[v][kk+1]=dis[u][kk];
                q.push(node(v,dis[v][kk+1],kk+1));
            }
        }
    }
}


int main()
{
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d",&start,&last);
    for(int i=1; i<=m; i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dijkstra(start);
    int ans=0x7f7f7f7f;
    for(int i=0;i<=k;i++)
    {
        ans=min(ans,dis[last][i]);
    }
    printf("%d\n",ans);
    return 0;
}