撰写分层图最短路，就是在分层图上解决最短路问题
一般模型为：
在一张图上，有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的过程是最好理解的
#include<cstdio>
#include<iostream>
#include<queue>
#include<utility>
#include<cstring>
using namespace std;
#define inf 0x3f3f3f
struct fuck
{
int to, len, ne;
}ed[100005];
int vis[10005][12];
int d[10005][12];
int head[10005];
int cnt = 0, n, m, k, st, en;
void init()
{
memset(vis, 0, sizeof(vis));
for (int s = 0; s <= n; s++)
{
for (int w = 0; w <= k; w++)
{
d[s][w] = inf;
}
head[s] = -1;
}
cnt = 0;
}
void add(int from, int to, int len)
{
ed[cnt].to = to;
ed[cnt].len = len;
ed[cnt].ne = head[from];
head[from] = cnt++;
}
void spfa()
{
d[st][0] = 0;
vis[st][0] = 1;
queue< pair<int,int> >q;
q.push(make_pair(st, 0));
while (!q.empty())
{
pair<int, int>t = q.front();
q.pop();
vis[t.first][t.second] = 0;
for (int s = head[t.first]; ~s; s = ed[s].ne)
{
if (d[t.first][t.second] + ed[s].len < d[ed[s].to][t.second])
{
d[ed[s].to][t.second] = d[t.first][t.second] + ed[s].len;
if (!vis[ed[s].to][t.second])
{
vis[ed[s].to][t.second] = 1;
q.push(make_pair(ed[s].to, t.second));
}
}
if (d[t.first][t.second] < d[ed[s].to][t.second+1]&&t.second<k)
{
d[ed[s].to][t.second+1] = d[t.first][t.second];
if (!vis[ed[s].to][t.second+1])
{
vis[ed[s].to][t.second+1] = 1;
q.push(make_pair(ed[s].to, t.second+1));
}
}
}
}
}
int main()
{
while (~scanf("%d%d%d", &n, &m, &k))
{
init();
scanf("%d%d", &st, &en);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
spfa();
printf("%d\n", d[en][k]);
}
return 0;
}