#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e9,N=10000;
int n,m,p;
int st,en,vis[11][20010],num[20010],dis[11][20010];
struct Graph{
int to,w,dep;
bool operator <(const Graph &x)const{
return x.dep<dep && x.w<w;
}
bool operator >(const Graph &x)const{
return x.dep>dep && x.w>w;
}
};
vector<Graph>g[20010];
priority_queue<Graph>q;
int main(){
cin>>n>>m>>p;
cin>>st>>en;
for(int i=0;i<=p;i++) for(int j=0;j<n;j++) dis[i][j]=MAXN;
for(int i=1,x,y,w;i<=m;i++){
cin>>x>>y>>w;
g[x].push_back({y,w,0});
g[y].push_back({x,w,0});
}
dis[0][st]=0;
q.push({st,0,0});
while(!q.empty()){
Graph k=q.top();
q.pop();
if(vis[k.dep][k.to]) continue;
vis[k.dep][k.to]=1;
for(Graph i:g[k.to]){
if(dis[k.dep][k.to]+i.w<dis[k.dep][i.to]){
dis[k.dep][i.to]=dis[k.dep][k.to]+i.w;
if(!vis[k.dep][i.to]) q.push({i.to,dis[k.dep][i.to],k.dep});
}
if(k.dep<p){
if(dis[k.dep+1][i.to]>dis[k.dep][k.to]){
dis[k.dep+1][i.to]=dis[k.dep][k.to];
if(!vis[k.dep+1][i.to]) q.push({i.to,dis[k.dep+1][i.to],k.dep+1});
}
}
}
}
int ans=2e9;
for(int i=0;i<=p;i++) ans=min(ans,dis[i][en]);
cout<<ans;
return 0;
}
hack 能过,样例没问题。 谢谢好心人出手相助!