<h1>定义</h1>

分层图最短路问题，一般是指我们在可以进行分层的图上进行最短路。
一般模型是：
在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。
题目链接

<h1>分析</h1>

其实这一题我们用动态规划的思想看，用disti表示免费了k次的最短路径
详细的转移请参考代码
然后跑最短路即可。

<h1>代码</h1>

/*
做这一题的时候不知道怎么回事，用指针就疯狂WA，最后写了数组才过。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <algorithm>

const int MAXN = 10000 + 5;
const int MAXM = 50000 + 5;
const int MAXK = 10 + 5;

int N,M,K,S,T;
int distMAXN;//disti表示第k层结点i到起点的最短距离
int head[MAXN],cnt;
bool inQueueMAXN;//inQueuei表示第k层的结点i是否在队列

struct Edge{
    int to,w,next;
}e[MAXM * 2];

inline void add(int u,int v,int w){
    e[++cnt].w = w;e[cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}

void spfa(){
    memset(dist,0x7f,sizeof(dist));
    memset(inQueue,false,sizeof(inQueue));
    std::queue<std::pair<int,int> > q;
    q.push(std::make_pair(S,0));
    inQueueS = true;
    distS = 0;
    while(!q.empty()){
        int v = q.front().first;
        int step = q.front().second;
        q.pop();
        inQueuev = false;
        for(int i = head[v];i;i = e[i].next){
            int to = e[i].to;
            if(distv + e[i].w < distto){ //同层转移
                distto = distv + e[i].w;
                if(!inQueueto){
                    inQueueto = true;
                    q.push(std::make_pair(to,step));
                }
            }
            if(distv < distto && step < K){ //异层转移
                distto = distv;
                if(!inQueueto){
                    inQueueto=1;
                    q.push(std::make_pair(to,step + 1));
                }
            }
        }
    }
    int ans = INT_MAX;
    for(int i = 0;i <= K;i++) //统计答案
        ans = std::min(ans,distT);
    printf("%d",ans);
}

int main(){
    scanf("%d%d%d%d%d",&N,&M,&K,&S,&T);
    for(int i = 1;i <= M;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    spfa();
    return 0;
}