分层图最短路，就是在分层图上解决最短路问题
一般模型为：
在一张图上，有k次机会可以通过一条边而不需要计算权值（免费过路），求从起点到终点的最短路线
常规思路：
想象将一个点拆分为k + 1个点，分别表示到这个点时，免费权消耗了0次，1次，2次......k次
这样实际我们可以把这k个点想象成对应dp的不同的状态
dis[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)}
这就提醒我们，我们的队列在加入到达某个点的同时，要分别记录到达这个点时的两种不同的状态，以免造成情况遗漏
也就是q[i][j]表示到第i个点时，第i个点在j的情况下我们消耗了几次免费过路权，j为0或是1,0表示没有消耗免费过路权，1表示消耗了免费过路权
到这里我们就能与上面的拆点联系上了，我们想，到了终点时，可能有：用了0次免费过路权，用了1次免费过路权，用了2次，用了3次....用了k次
也就是k+1种可能状态，此时我们把这k+1种状态，每种状态都想象成原本的这个点拆分出来的一个点，也就相当于这个点拆分出了k+1个点，就和上面接上了
然后我们合理外推，对于每一个点都可能出现这样的情况，也就相当于每一个点都拆分成了k+1个点，这n*(k+1)个点之间彼此连接，跑最短路，这样可能有点抽象
实际上把这想象成一个dp的过程是最好理解的
例题1：move(集训考试题)
题目描述
给定一张地图一共有 n 个城市，城市编号为 0 ～ n - 1，这 n 个城市通过 m
条铁路连接(走一条铁路视为乘车一次)。而小A 想从城市 s 出发，到 达城市 t
结束。小A 可以免费乘车 k 次，现在他想知道，他这 次旅游的最少花费是多少?
输入格式
第一包含三个整数 n, m, k，含义见题目描述。
第二有两个整数 s, t，表示小A 的出发城市和结束城市。
接下来 m 行，每行三个整数 x, y, z，表?在城市 x 和 y 之间有一条铁路相
连，乘车花费为 z。
输出格式
输出一行，一个整数表示答案。
样例输入
5 6 1
0 4
0 1 5
1 2 5
2 3 5
3 4 5
2 3 3
0 2 100
样例输出
8
数据范围
对于 30% 的数据， 2 ≤ n ≤ 50, 1 ≤ m ≤ 300, k = 0;
对于 50% 的数据， 2 ≤ n ≤ 600, 1 ≤ m ≤ 6000, 0 ≤ k ≤ 1;
很标准的模板型题目。
思路就是上面的思路，不加赘述，代码实现口胡不好说，直接读代码吧=-=