ARX：我今天上午做了两个分层图最短路的题，可简单了……

概念

分层图最短路是指在可以进行分层图的图上解决最短路问题。
一般模型是：
在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。

算法思路

这是一个类似于DP的思路。
用直接通过的边把整个图分成k个子图，其中k为可以直接通过的边的个数。在此基础上，我们直接跑最短路算法就可以了。

算法细节

在处理子图与子图之间的关系时，由于连接两个子图的路径是可以直接通过的，所以我们在记录下一层的路径长度时，转移方程为:
if(d[edge[i].to][level + 1] < d[u][level] && level < k) d[edge[i].to][level + 1] = d[u][level];
其中edge[i]是一条以节点u为起点的边。注意，由于图的层数有限，所以level < k这一条件一定不要忘记加。
附一下代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define INF 2147483647

using namespace std;

struct node{
    int k,dis,used;
    bool operator < ( const node &x )const{return x.dis < dis;}
};

priority_queue<node> que;

long long n,m,k,s,t,d[50005],cnt,D[50005][15],v[50005][15]; 

struct Edge{
    int to,next,x;
}edge[2000005];

void add(int x,int y,int a)
{
    edge[++cnt].to = y;
    edge[cnt].x = a;
    edge[cnt].next = d[x];
    d[x] = cnt;
}

int main()
{
    int x,y,a;
    scanf("%lld%lld%lld",&n,&m,&k);
    scanf("%d%d",&s,&t);
    for(register int i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&x,&y,&a);
        add(x,y,a);
        add(y,x,a);
    }
    que.push((node){s,0,0});
    for(register int i = 0; i <= n; i++)
        for(register int j = 0; j <= k; j++) 
            D[i][j] = INF;
    D[s][0] = 0;
    while(!que.empty())
    {
        node u = que.top();
        que.pop();
        int kk = u.k,level = u.used;
        if(v[u.k][u.used]) continue;
        v[u.k][u.used] = 1;
        for(register int i = d[kk]; i; i = edge[i].next)
        {
            
            int too = edge[i].to;
            if(D[too][level] > D[kk][level] + edge[i].x)
            {
                D[too][level] = edge[i].x + D[kk][level];
                que.push((node){too,D[too][level],level});
            }
            if(level < k && D[too][level + 1] > D[kk][level])
            {
                D[too][level + 1] = D[kk][level];
                que.push((node){too,D[too][level + 1],level + 1});
            }
        }
    }
    long long  ans = INF;
    for(register int i = 0; i <= k; i++) ans = min(ans,D[t][i]);
    printf("%lld\n",ans);
    return 0;
}

推荐练习题目：飞行路线、冻结、回家的路