RT。由于没法下数据而且神奇的过了样例蒟蒻没看出来 机房大佬也没看出来 有没有神犇来给我看看

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
int to[200001],head[200001],nxt[200001],wei[200001],vis[200001],dis[200001],cnt = 0,n,m,k;
const int inf = 0x3f3f3f3f;
void add(int u,int w,int v) {
    cnt++;
    to[cnt] = w;
    wei[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
struct popo {
    int now,dis;
    bool operator<(popo a) const {
        return dis > a.dis;
    }
};
void dijk() {
    priority_queue<popo> q;
	q.push((popo){1,0});
	dis[1] = 0;
	while(!q.empty()) {
        popo p = q.top();
        int now = p.now;
        //int dis = p.dis;
        vis[now] = 1;
        q.pop();
        for(int i = head[now]; i; i = nxt[i]) {
            if(!vis[to[i]] && (dis[to[i]]>dis[now]+wei[i])) {
                dis[to[i]] = dis[now]+wei[i];
                q.push((popo){to[i],dis[to[i]]});
            }
        }
	}
}
signed main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int a,b,t;
        cin >> a >> b >> t;
        for(int j = 0; j <= k; j++) {
            add(a+n*j,b+n*j,t);
            add(b+n*j,b+n*j,t);
        }
        for(int j = 0; j < k; j++) {
            add(a+n*j,b+n*(j+1),t/2);
            add(b+n*j,a+n*(j+1),t/2);
        }
    }
    for(int i = 1; i <= k*n+n; i++) {
        dis[i] = inf;
    }
    dijk();
    int ans = inf;
    for(int i = 0; i <= k; i++) {
        ans = min(ans,dis[(i+1)*n]);
    }
    cout << ans;
    return 0;
}