二维/分层图模版题解(例题：传送门)

· · 题解

# 传送门的传送门

Description $FJ$从家到牧场的地区可以看作一个$N$个点和$M$条双向边的图，家在1号点，牧场在$N$号点。 现在FJ掌握了现代科技，他现在要将一些道路的两端修建双向传送的传送门，这样可以把通过的时间变为$0$。 现在FJ最多可以建$K$个传送门，FJ想知道他从家到牧场最少需要多少时间？ $Input Format

第一行，三个数N，M，K

接下来M 行，每行三个数，表示一条边的两端和长度

Output Format

一个数，表示最少要用多长时间 Sample 样例输入 4 4 1 1 2 10 2 4 10 1 3 1 3 4 100 样例输出 1

分层图定义： 分层图--------可以理解为有多个平行的图 第i层表示用了i张免费卷后到达每个点的最短路 显然，可以在同层跑最短路，而低层可以到高层 这就满足了在不同层间无后效性的拓展 于是我们可以设状态 其实简洁来说，以这道题为例就是相较单纯的距离dis多了一个目前使用多少传送门的状态 在题中可以用t表示，将原先dijk算法中的flag[]和dis[],更改为二维的形式，如：dis[点的坐标][使用传送门的数量] ，flag同理。 接下来是对dijk算法中的更改，首先对优先队列的定义需要三个变量：点的坐标，距离，使用传送门的数量，用距离存小根堆。 剩下需要分两个判断 是否使用传送门 dis[y][t]>dis[x][t]+e[i].w不使用 dis[y][t+1]>dis[x][t]使用 之后依次循环直到空。

代码如下


using namespace std;
#define maxx 11454810
#define N 10011
int dis[N][30]={0},head[100000];
int flag[N][30];
int n,m,k,f,cnt=0,p;

int tim[100000]={0};
int ans[100000]={0};
int w[100000]={0};
int ei;
struct edge{
    int to,w,next=0;
}e[100000];

struct df{
    int x,t,dis;
};
bool operator<(const df & a,const df & b)
{
    if(a.dis==b.dis)
    {
        return a.t>b.t;
    }
    else
    {
        return a.dis>b.dis;
    }
}
priority_queue<df>q;

void Shion()
{
    for(int i=0;i<=N-1;i++)
    {
        for(int j=0;j<=25;j++)
        {
            dis[i][j]=0x7fffffff;
        }
    }
    dis[1][0]=0;
    q.push(df{1,0,0});
    flag[1][0]=1;
    while(!q.empty())
    {
        df tmp=q.top();
        int x=tmp.x,t=tmp.t;
        q.pop();
        flag[x][t]=1;  //?

        for(int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if(!flag[y][t]&&dis[y][t]>dis[x][t]+e[i].w) //不使用
            {
                dis[y][t]=dis[x][t]+e[i].w;
                if(!flag[y][t])
                {
                    q.push(df{y,t,dis[y][t]});  
                }
            }
            if(t<k)
                if(!flag[y][t+1]&&dis[y][t+1]>dis[x][t])//使用
                {
                    dis[y][t+1]=dis[x][t];
                    if(!flag[y][t+1])
                    {
                        q.push(df{y,t+1,dis[y][t+1]});
                    }
                }
        }
    }
}
void add(int u,int v,int w) //起点u, 终点v, 权值w
{   
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
signed main()
{   
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    Shion();
    int minn=0x7fffffff;
    for(int i=0;i<=k;i++)
    {
        if(dis[n][i]<minn)
        {
            minn=dis[n][i];
        }
    }
    cout<<minn;
}