致敬传奇卡空间王

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 2, M = 5 * 1e4 + 2, K = 21, INF = 0x3f3f3f3f;
int n, m, k, dis[N * K];
vector<pair<int, int>> Graph[N * K];
set<pair<int, int> > heap;
void add_edge(int u, int v, int w){
    Graph[u].push_back(make_pair(v, w));
}
void dijkstra(){
    memset(dis, 0x3f, sizeof(dis));
    heap.insert(make_pair(1, dis[1] = 0));
    while(!heap.empty()){
        int u = heap.begin()->first;
        int d = heap.begin()->second;
        heap.erase(heap.begin());
        if(d > dis[u]) continue;
        for(int i = 0; i < Graph[u].size(); i++){
            const int & v = Graph[u][i].first;
            if(dis[v] > dis[u] + Graph[u][i].second){
                dis[v] = dis[u] + Graph[u][i].second;
                heap.insert(make_pair(v, dis[v]));
            }
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &k);
    int u, v, w;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
        for(int j = 1; j <= k; j++){
            add_edge(u + j * n, v + j * n, w);
            add_edge(v + j * n, u + j * n, w);
            add_edge(u + j * n - n, v + j * n, 0);
            add_edge(v + j * n - n, u + j * n, 0);
        }
    }
    dijkstra();
    int ans = INF;
    for(int j = 0; j <= k; j++){
        ans = min(ans, dis[n + j * n]);
    }
    printf("%d\n", ans);
    return 0;
}