分层图dij

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int to[N<<1],nxt[N<<1],bgn[N],e=0,w[N<<1];
void add(int x,int y,int z){
	e++,to[e]=y,w[e]=z;
	nxt[e]=bgn[x],bgn[x]=e;
}int n,m,k,s,t,u,v,z,ret=0x3f3f3f3f,dis[N][20],vis[N][20];
struct node{
	int id,how_many,val;
};
bool operator < (node a,node b){
	return a.val>b.val;
}priority_queue<node>q;
void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s][0]=0;
	q.push((node){s,0,0});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.id,now_many_used=tmp.how_many;
		if(vis[x][now_many_used]){
			continue;
		}vis[x][now_many_used]=1;
		for(int j=bgn[x];j;j=nxt[j]){
			int y=to[j],z=w[j];
			if(dis[y][now_many_used]>dis[x][now_many_used]+z){
				dis[y][now_many_used]=dis[x][now_many_used]+z;
				q.push((node){y,now_many_used,dis[y][now_many_used]});
			}if(now_many_used<k&&dis[y][now_many_used+1]>dis[x][now_many_used]){
				dis[y][now_many_used+1]=dis[x][now_many_used];
				q.push((node){y,now_many_used+1,dis[y][now_many_used+1]});
			}
		}
	}
}int main(){
	scanf("%d%d%d",&n,&m,&k);
	scanf("%d%d",&s,&t);
	s++,t++;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&z);
		u++,v++;
		add(u,v,z);
		add(v,u,z);
	}dijkstra(s);
	for(int i=0;i<=k;i++){
		ret=min(ret,dis[t][i]);
	}printf("%d",ret);
	return 0;
}