首先看到点数，就考虑拆点。
把每一个点拆成k个点，分别表示已经吃了k次免费午餐的距离。
然后大力跑堆优化dij即可。可以用pair加伪函数套STL。
特别要注意是小根堆。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
struct ee{
int v;int w;int nxt;
}e[100005];
int h[10005],et=0,f[10005][12],n,m,k,s,t;
inline void add(const int &u,const int &v,const int &w){
e[++et]=(ee){v,w,h[u]};
h[u]=et;
}
typedef pair<int,int> pii;
struct cmp{
bool operator ()(const pii &A,const pii &B){
return f[A.first][A.second]>f[B.first][B.second];
}
};
priority_queue<pii,vector<pii>,cmp> q;
void bfs(int s){
pii p(s,0);
q.push(p);
while(!q.empty()){
p=q.top();
q.pop();
for(int i=h[p.first];i;i=e[i].nxt){
if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){
f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;
q.push((pii){e[i].v,p.second});
}
if(p.second+1<=k){
if(f[e[i].v][p.second+1]>f[p.first][p.second]){
f[e[i].v][p.second+1]=f[p.first][p.second];
q.push((pii){e[i].v,p.second+1});
}
}
}
}
}
void init(){
scanf("%d%d%d",&n,&m,&k);
scanf("%d%d",&s,&t);
memset(f,0x3f,sizeof(f));
int u,v,w;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
if(u==v){
continue;
}
add(u,v,w);
add(v,u,w);
}
for(int i=0;i<=k;++i){
f[s][i]=0;
}
bfs(s);
int ans=0x3f3f3f3f;
for(int i=0;i<=k;++i){
ans=Min(ans,f[t][i]);
}
printf("%d",ans);
}
int main(){
init();
return 0;
}
