// problem :  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
int n, m, k;
std::vector<PII> e[55];

int dis[55][55];
bool vis[55];
struct node {
    int x, d;
    bool operator < (const node & k) const {
        return d > k.d;
    }
};
void dijkstra() {
    priority_queue<node> q;

    q.push({1, 0});
    memset(dis, 127, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1][0] = 0;
    while (!q.empty()) {
        node u = q.top(); q.pop();
        int x = u.x;
        if (vis[x]) continue;
        vis[x] = true;
        for (auto [y, w] : e[x]) {
            if (vis[y]) continue;

            for (int i = 0; i <= k; ++i) {
                if (dis[x][i] + w < dis[y][i]) {
                    dis[y][i] = dis[x][i] + w;
                    q.push({y, dis[y][i]});
                }
                if (i != k && dis[x][i] + w / 2 < dis[y][i + 1]){
                    dis[y][i + 1] = dis[x][i] + w / 2;
                    q.push({y, dis[y][i + 1]});
                }
            }
        }
    }
    int ans = 1 << 30;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dis[n][i]);
    }
    printf("%d\n", ans);
}
int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) {
        int x, y, w;
        scanf("%d %d %d", &x, &y, &w);
        e[x].push_back(make_pair(y, w));
        e[y].push_back(make_pair(x, w));
    }
    dijkstra();
    
    return 0;
}

下边也有个贝尔曼的方法，过了。上面的dijkstra为啥不行呢？

// problem :  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
struct edge{
    int x, y, z;
}e[4005];
int n, m, k;
int cnt = 0;
int f[505][55];
void bm(int s, int t){
    memset(f, 127, sizeof(f));
    f[s][0] = 0;
    while(true){
        bool ok = false;
        for(int i = 1; i <= cnt; ++i){
            int x = e[i].x, y = e[i].y, z = e[i].z;
            for(int j = 0; j <= k; ++j){
                if(f[x][j] < 1 << 30){
                    if(f[x][j] + z < f[y][j]){
                        f[y][j] = f[x][j] + z;
                        ok = true; 
                    }
                    if(j != k && f[x][j] + z / 2 < f[y][j + 1]){
                        f[y][j + 1] = f[x][j] + z / 2;
                        ok = true;
                    }
                }
            }
        }
        if(!ok)
            break;
    }
    int ans = 1 << 30;
    for(int i = 0; i <= k; ++i)
        ans = min(ans, f[n][i]);
    printf("%d\n", ans);
}
int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= m; ++i){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        e[++cnt].x = x, e[cnt].y = y, e[cnt].z = z;
        e[++cnt].x = y, e[cnt].y = x, e[cnt].z = z;
    }
    bm(1, n);
    return 0;
}