再来一个简单的分层图练习：

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

输入格式

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。
第二行有两个整数，s,ts,t，分别表示他们出行的起点城市编号和终点城市编号。
接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。

输出格式

只有一行，包含一个整数，为最少花费。

输入输出样例

输入
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 \le n \le 50,1 \le m \le 300,k=02≤n≤50,1≤m≤300,k=0;
对于50%的数据,2 \le n \le 600,1 \le m \le 6000,0 \le k \le 12≤n≤600,1≤m≤6000,0≤k≤1;
对于100%的数据,2 \le n \le 10000,1 \le m \le 50000,0 \le k \le 102≤n≤10000,1≤m≤50000,0≤k≤10,0 \le s,t<n,0 \le a,b<n,a\neq b,0 \le c \le 10000≤s,t<n,0≤a,b<n,a≠b,0≤c≤1000

题 目 链 接

很明显，直接建立 k 层分层图，然后 dp 层与层之间的关系即可。

层与层之间的关系就是当前是否使用免费飞行，以及上一层使用了几次免费飞行，构建一下 dp 转移方程就好了。

注意：这道题 spfa 会被卡死，要用 dijkstra 就AC了

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10; 
int n,m,num,st,ed,dst[N][11],vis[N][11];
int head[N],nex[M],to[M],w[M],tot;
struct node{
	int u,k,w;
};
bool operator < (node a,node b){
	return a.w>b.w;
}
void add(int a,int b,int c){
	w[++tot]=c;	to[tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dijkstra(){
	priority_queue<node> pq; pq.push({st,0,0});
	memset(dst,0x3f,sizeof dst);	dst[st][0]=0;
	while(pq.size()){
		int u=pq.top().u;	int k=pq.top().k;	int c=pq.top().w; pq.pop();
		if(vis[u][k])	continue;	vis[u][k]=1;
		for(int i=head[u];i;i=nex[i]){
			int v=to[i];	int val=w[i];
			if(dst[v][k]>dst[u][k]+val){
				dst[v][k]=dst[u][k]+val;
				pq.push({v,k,dst[v][k]});
			}
			if(k<num&&dst[v][k+1]>dst[u][k]){
				dst[v][k+1]=dst[u][k];
				pq.push({v,k+1,dst[v][k+1]});
			}
		}
	}
}
int main(){
	cin>>n>>m>>num>>st>>ed;
	while(m--){
		int a,b,c;	cin>>a>>b>>c;	add(a,b,c);	add(b,a,c);
	}
	dijkstra();
	int res=0x3f3f3f3f;
	for(int i=0;i<=num;i++)	res=min(res,dst[ed][i]);
	cout<<res<<endl; 
	return 0;
}