@[larryia](/user/1042486)
[关于Hack](https://www.luogu.com.cn/discuss/798248)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1e4 + 10;
struct edge {
int v, w;
};
vector<edge> e[N];
int d[N], vis[N];
int n, m, k, s, t;
void dij(int s) {
memset(d, 0x3f, sizeof d);
d[s] = 0;
priority_queue<pair<int, int> > q;
q.push({0, s});
while (q.size()) {
auto temp = q.top();
q.pop();
int u = temp.second;
if (vis[u]) continue;
vis[u] = 1;
for (auto ed: e[u]) {
int v = ed.v, w = ed.w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push({-d[v], v});
}
}
}
}
int main() {
cin >> n >> m >> k >> s >> t;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
for (int j = 0; j <= k; j++) {
e[a + j * n].push_back({b + j * n, c});
e[b + j * n].push_back({a + j * n, c});
if (j < k) {
e[a + j * n].push_back({b + j * n + n, 0});
e[b + j * n].push_back({a + j * n + n, 0});
}
}
}
dij(s);
int ans = d[t];
for (int i = 1; i <= k; i++) {
ans = min(ans, d[t + i * n]);
}
cout << ans;
return 0;
}
```
by Rzf_AK_IOI @ 2024-03-30 11:37:15