飞行路线

95pt 最后一个测试的挂了，答案是0

#include<bits/stdc++.h>
using namespace std;
struct ede{
	int v,w;
};
struct kkk{
	int u,k,w;
	bool operator < (const kkk a)const{
		return w > a.w;
	}
};
vector<ede> g[100210];
int dis[100010][22],K;
bool inq[100010][22];
void dijk(int s){
	priority_queue<kkk> q;
	memset(dis,0x3f,sizeof(dis));
	q.push(kkk{s,0,0});
	dis[s][0] = 0;
	while(!q.empty()){
		kkk U = q.top();
		q.pop();
		int u = U.u,k = U.k;
		if(k > K+1)continue;
		if(inq[u][k])continue;
		inq[u][k] = 1;
		for(ede vis:g[u]){
			int v = vis.v,w = vis.w;
			if(dis[v][k] > dis[u][k]+w){
				dis[v][k] =  dis[u][k]+w;
				if(!inq[v][k]){
					q.push(kkk{v,k,dis[v][k]});
				}
			}
			if(dis[v][k+1] > dis[u][k]){
				dis[v][k+1] = dis[u][k];
				if(!inq[v][k+1]){
					q.push(kkk{v,k+1,dis[v][k+1]});
				}
			}
		}
	}
}
int n,m;
int s,t;
int main(){
	cin>>n>>m>>K;
	cin>>s>>t;
	for(int i = 1;i <= m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dijk(s);
	int ans = 1e9+1;
	for(int i = 0;i <= K;i++){
		ans = min(ans,dis[t][K]);
	}
	cout<<ans;
	return 0;
}