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

WA on #3 & #8.

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int maxn = 3 * 1e6 + 10;
const int inf = 2147483647;
int n, m, k, s, t, ans = inf;
int h[maxn], val[maxn], to[maxn], nxt[maxn], idx;
int dis[maxn];
bool vis[maxn];

void add(int a, int b, int c) {
	to[idx] = b;
	val[idx] = c;
	nxt[idx] = h[a];
	h[a] = idx ++;
}

struct node {
	long long v, w;
	friend bool operator <(node a, node b) {
		return a.w > b.w;
	}
} tmp;

priority_queue<node> q;

void Dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	tmp.v = s, tmp.w = 0;
	q.push(tmp);
	while (!q.empty()) {
		int u = q.top().v;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (int i = h[u]; i; i = nxt[i]) {
			int j = to[i];
			if (dis[j] > (long long)dis[u] + val[i]) {
				dis[j] = dis[u] + val[i];
				tmp.w = dis[j], tmp.v = to[i];
				q.push(tmp);
			}
		}
	}
}

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	cin >> s >> t;
	for (int i = 0, a, b, c; i < m; i++) {
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
		for (int j = 1; j <= k; j++) {
			add(a + j * n, b + j * n, c);
			add(b + j * n, a + j * n, c);
			add(a + j * n - n, b + j * n, 0);
			add(b + j * n - n, a + j * n, 0);
		}
	}
	Dijkstra();
	int ans=inf;
	for (int j = 0; j <= k; j++)
		if (dis[t + j * n] < ans) ans = dis[t + j * n];
	cout << ans;
	return 0;
}