定义

分层图最短路一般用于解决一种特殊的最短路问题：

给定一个图，在图上可以进行 $k$ 次决策（一般 $k \leq 10$），每次决策并不影响图的结构，只会影响目前的状态/代价。

一般可以将决策前的状态 和 决策后的状态 连接一条边，权值为决策代价。

总体来说，套路如下：

  1. 给定 $k$ 次决策，将图复制成 $k+1$ 份，分别表示在进行了第 $i$ 次决策后的状态，每一份复制是一层图。
  2. 从第 $i$ 层，连单向边到第 $i+1$ 层。（有的时候并不需要专门连边，可以在跑最短路的时候顺便转移状态）
  3. 跑最短路。

例题

例1 洛谷P4568 [JLOI2011]飞行路线

题意

给定 $n$ 个节点，$m$ 条边的无向连通图，每个边具有一个权值。

现给出一个整数 $k$，代表我们可以免费走过最多 $k$ 条边。

给出起点 $s$ 和终点 $t$，求 $s$ 到 $t$ 的最短路？

其中，$2 \leq n \leq 10^4, 1 \leq m \leq 5 \times 10^4, 0 \leq k \leq 10$

题解

分层图模版题。

我们建立 $k+1$ 层图，当我们位于 第 $j$ 层的 $i$ 节点时，代表我们此时走到了节点 $i$，已经用掉了 $j$ 次免费机会。

建图时：（实际上并不需要建图，跑dijkstra的时候顺便转移即可）

  1. 同一层的权值就和原图一样。
  2. 从 第 $i$ 层，连单向边到第 $i+1$ 层的权值为 $0$。

然后跑一下Dijkstra就可以了。

Dijkstra 有以下几个注意的点：

  1. priority_queue<node> pq;，直接定义 node 的 operator< 函数即可，但是要注意一些细节，如下： 
    struct node {
     int u, k, d;
     // 1. 注意，两个const都需要
     // 2. pq默认是大顶，所以要反过来用 > 
     bool operator<(const node& other) const {
         return d > other.d;
     }
 };
 priority_queue<node> pq;
  2. Dijkstra使用了一个 int dis[maxn][11] 数组，这是需要在 push() 时更新的，而不是 pop() 时才更新。在 push() 之前先看一下 dis 是否比当前的小，如果小，才 push()。这大大减少了pq 内的元素数量。
代码 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+5;
const int maxm = 5e4+5;

int dis[maxn][11], head[maxn], ecnt = 1;
bool vis[maxn][11];
struct Edge {
    int to, nxt, w;
} edges[maxm<<1];
void addEdge(int u, int v, int w) {
    Edge e = {v, head[u], w};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

struct node {
    int u, k, d;
    // 注意，两个const都需要
    // pq默认是大顶，所以要反过来用 > 
    bool operator<(const node& other) const {
        return d > other.d;
    }
};
priority_queue<node> pq;

int n,m,K,s,t;
void dijkstra() {
    pq.push({s, 0, 0});
    while (!pq.empty()) {
        node cur = pq.top();
        pq.pop();
        int u = cur.u, k = cur.k, d = cur.d;
        if (vis[u][k]) continue;
        vis[u][k] = 1;
        for (int e = head[u]; ~e; e = edges[e].nxt) {
            int to = edges[e].to, w = edges[e].w;
            if (dis[to][k] > d + w) {  // 同一层
                dis[to][k] = d + w;
                pq.push({to, k, d + w});
            }
            if (k+1 <= K && dis[to][k+1] > d) {  // 下一层
                dis[to][k+1] = d;
                pq.push({to, k+1, d});
            }
        }
    }
}

int main() {
    fastio;
    cin >> n >> m >> K;
    cin >> s >> t;
    fill(head, head+maxn, -1);
    memset(dis, 63, sizeof(dis));
    while (m--) {
        int u,v,w; cin >> u >> v >> w;
        addEdge(u,v,w);
        addEdge(v,u,w);
    }
    dijkstra();
    int ans = 1e9;
    for (int k = 0; k <= K; k++) ans = min(ans, dis[t][k]);
    cout << ans << endl;
}

例2 洛谷P3119 [USACO15JAN]Grass Cownoisseur G

见 强连通分量（SCC）的这里