代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+100,M=5e4+100;
int n,m,K,s,t,a,b,w,idx=1,head[N];
int dis[N][15];
bool vis[N];
struct Edge{
	int to,next,w;
}e[M];
struct node{
	int dis,id,k;
};
struct cmp{
	bool operator()(node a,node b){
		return a.dis>b.dis;
	}
};
priority_queue<node,vector<node>,cmp> p;
void add(int a,int b,int w){
	e[idx].to=b;
	e[idx].w=w;
	e[idx].next=head[a];
	head[a]=idx;
	idx++;
}
void dij(int s){
	memset(dis,0x3f3f3f3f,sizeof(dis));
	node s1;
	s1.dis=0;
	s1.k=0;
	s1.id=s;
	dis[s][0]=0;
	p.push(s1);
	while(!p.empty()){
		node now=p.top();
		p.pop();
		if(vis[now.id]) continue;
		vis[now.id]=1;
		int nk=now.k;
		for(int i=head[now.id];i;i=e[i].next){
			int v=e[i].to;
			if(vis[v]) continue;
			if(dis[v][nk]>dis[now.id][nk]+e[i].w){
				dis[v][nk]=dis[now.id][nk]+e[i].w;
				node l;
				l.k=nk;
				l.id=v;
				l.dis=dis[v][nk];
				p.push(l);
			}
			if(nk<K&&dis[v][nk+1]>dis[now.id][nk]){
				dis[v][nk+1]=dis[now.id][nk];
				node l;
				l.k=nk+1;
				l.id=v;
				l.dis=dis[v][nk+1];
				p.push(l);
			}
		}
	}
}
int main(){
	cin>>n>>m>>K;
	cin>>s>>t;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&w);
		add(a,b,w); 
	}
	dij(s);
	int ans=0x3f3f3f3f;
	for(int i=0;i<=K;i++){
		//cout<<dis[t][i];
		ans=min(ans,dis[t][i]);
	}
	cout<<ans;
	
	return 0;
}