// 分层图最短路 分层建图 Dijkstra 算法 O(mk*log(nk))
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 10005 * 11;

vector<pii> g[N];

int n, m, k, s, t;
int d[N];

void dijkstra()
{
  memset(d, 0x3f, sizeof d);d[s] = 0;
  priority_queue<pii, vector<pii>, greater<pii>> q;
  q.emplace(0, s);
  while (q.size())
  {
    pii t = q.top();q.pop();
    int dd = t.first, u = t.second;
    if (dd != d[u])
      continue; // 不是第一次出队就跳过
    for (auto i: g[u])
    {
      int v = i.first, w = i.second;
      if (d[v] > d[u] + w)
      {
        d[v] = d[u] + w;
        q.emplace(d[v], v);
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k >> s >> t;
  for (int a, b, c; m--;)
  {
    cin >> a >> b >> c;
    g[a].push_back({b, c}), g[b].push_back({a, c}); // 0层双向边
    for (int i = 1; i <= k; i++)
    {
      g[a + i * n].push_back({b + i * n, c}), g[b + i * n].push_back({a + i * n, c});             // 层内双向边
      g[a + (i - 1) * n].push_back({b + i * n, 0}), g[b + (i - 1) * n].push_back({a + i * n, 0}); // 层间单向边
    }
  }
  dijkstra();
  int ans = 2e9;
  for (int i = 0; i <= k; i++)
    ans = min(ans, d[t + i * n]); // 没走完k+1层，可能已经最小
  cout << ans;
}

// 分层图最短路 二维数组 Dijkstra 算法 O(mk*log(nk))
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ipi pair<int, pii>
using namespace std;

const int N = 10005;

vector<pii> g[N];

int n, m, k, s, t;
int d[N][11]; // d[i][j]表示到达i用了j次免费的最小花费
bool vis[N][11];

void dijkstra()
{
  memset(d, 0x3f, sizeof d);
  d[s][0] = 0;
  priority_queue<ipi, vector<ipi>, greater<ipi>> q;
  q.push({0, {s, 0}});
  while (!q.empty())
  {
    auto t = q.top().second; q.pop();
    int u = t.first, c = t.second;
    if (vis[u][c]) continue;
    vis[u][c] = 1;
    for (auto i : g[u])
    {
      int v = i.first, w = i.second;
      if (d[v][c] > d[u][c] + w)
      { // 层内走路
        d[v][c] = d[u][c] + w;
        q.push({d[v][c], {v, c}});
      }
      if (c < k && d[v][c + 1] > d[u][c])
      { // 层间走路
        d[v][c + 1] = d[u][c];
        q.push({d[v][c + 1], {v, c + 1}});
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k >> s >> t;
  for (int i = 0, a, b, c; i < m; i++)
  {
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }

  dijkstra();
  cout << *min_element(d[t], d[t] + k + 1); // 没走完k+1层，可能已经最小
}

套路题，分层图。

以样例为例（使用 @EternalAlexander 这位dalao的OI Painter绘制）：

各层内部正常连边，各层之间从上到下连权值为0的边。每向下跑一层，就相当于免费搭一次飞机。跑一遍从$s$到$t+n*k$的最短路即可。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<utility> 
#include<functional>

int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
    {
        c=getchar();
    }
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

using std::priority_queue;
using std::pair;
using std::vector;
using std::make_pair;
using std::greater;

struct Edge
{
    int to,next,cost;
}edge[2500001];
int cnt,head[110005];

void add_edge(int u,int v,int c=0)
{
    edge[++cnt]=(Edge){v,head[u],c};
    head[u]=cnt;
}

int dis[110005];
bool vis[110005];
void Dijkstra(int s)
{
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > points;
    points.push(make_pair(0,s));
    while(!points.empty())
    {
        int u=points.top().second;
        points.pop();
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i;i=edge[i].next)
            {
                int to=edge[i].to;
                if(dis[to]>dis[u]+edge[i].cost) 
                {
                    dis[to]=dis[u]+edge[i].cost;
                    points.push(make_pair(dis[to],to));
                }
            }
        }
    }
}

int main()
{
    int n=Read(),m=Read(),k=Read(),s=Read(),t=Read();
    int u,v,c;
    for(int i=0;i<m;++i)
    {
        u=Read(),v=Read(),c=Read();
        add_edge(u,v,c);
        add_edge(v,u,c);
        for(int j=1;j<=k;++j)
        {
            add_edge(u+(j-1)*n,v+j*n);
            add_edge(v+(j-1)*n,u+j*n);
            add_edge(u+j*n,v+j*n,c);
            add_edge(v+j*n,u+j*n,c);
        }
    }
    for(int i=1;i<=k;++i)
	{
		add_edge(t+(i-1)*n,t+i*n);
	}//预防奇葩数据
    Dijkstra(s);
    printf("%d",dis[t+k*n]);
    return 0;
}