$WA\ on\ 3,6$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = 2010, K = N, INF = 1e9;
int n, m, k;
int h[N * K + N], e[4 * M * K + 2 * M], w[4 * M * K + 2 * M], ne[4 * M * K + 2 * M], idx;
int get(int Floor, int id){
    return Floor * n + id;
}
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dist[N * K + N];
bool st[N];
void dijkstra(int S){
    for (int i = 0; i < N * K + N; i ++ ) dist[i] = INF;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, S});
    dist[S] = 0;
    while (q.size()){
        int id = q.top().y;
        q.pop();
        if (st[id]) continue;
        st[id] = true;
        for (int i = h[id]; ~i; i = ne[i]){
            int j = e[i];
            if (dist[j] > dist[id] + w[i]){
                dist[j] = dist[id] + w[i];
                q.push({dist[j], j});
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    memset(h, -1, sizeof h);
    while (m -- ){
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
        for (int j = 0; j < k; j ++ ){
            add(get(j, u), get(j + 1, v), w / 2);
            add(get(j, v), get(j + 1, u), w / 2);
            add(get(j + 1, u), get(j + 1, v), w);
            add(get(j + 1, v), get(j + 1, u), w);
        }
    }
    dijkstra(1);
    int res = INF;
    for (int i = 0; i <= k; i ++ )
        res = min(res, dist[get(i, n)]);
    printf("%d\n", res);
    return 0;
}