https://www.luogu.com.cn/record/96547105

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 5e5 + 5, K = 42;
struct edge {
	int next, to, w;
} e[M * K];
struct node {
	int pos, w;
	node(int _, int __) :
		pos(_), w(__) {}
	bool operator < (const node& x) const {
		return x.w < w;
	}
};
int n, m, k, s, t, u, v, w, cnt, ans = INT_MAX, head[N * K], dis[N * K];
bool vis[N * K];
priority_queue<node> q;
void add(int u, int v, int w) {
	e[++ cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void dijkstra(int s) {
	dis[s] = 0, q.push(node(s, 0));
	while (!q.empty()) {
		node u = q.top(); q.pop();
		if (vis[u.pos]) continue;
		vis[u.pos] = true;
		for (int i = head[u.pos]; i; i = e[i].next) {
			int v = e[i].to;
			if (dis[v] > dis[u.pos] + e[i].w) {
				dis[v] = dis[u.pos] + e[i].w;
				if (!vis[v]) q.push(node(v, dis[v]));
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(dis, 0x3f, sizeof dis);
	cin >> n >> m >> k, s = 1, t = n;
	for (int i = 1; i <= m; i ++) {
		cin >> u >> v >> w, add(u, v, w), add(v, u, w);
		for (int j = 1; j <= k; j ++) {
			add(u + n * j, v + n * j, w);
			add(v * n * j, u * n * j, w);
			add(u + n * (j - 1), v + n * j, w >> 1);
			add(v + n * (j - 1), u + n * j, w >> 1);
		}
	}
	dijkstra(s);
	for (int i = 0; i <= k; i ++)
		ans = min(ans, dis[n * (i + 1)]);
	cout << ans << '\n';
	return 0;
}