OK AC了
警示后人:
```cpp
vis[u][k] = 1; // Important :是标记一个点的第某个状态(即拆成 k + 1 个点后的其中一个点。),而不是整个点!
```
```cpp
// ZZQF5677 | 模拟考试 | 20231020 | T1
#include <bits/stdc++.h>
using namespace std;
long long n, m, K, s, t;
// star
long long head[10005], ecnt;
struct EDGE {
long long v, w, nex;
} e[500005 * 3];
void add(long long u, long long v, long long w) {
ecnt++;
e[ecnt].v = v;
e[ecnt].w = w;
e[ecnt].nex = head[u];
head[u] = ecnt;
}
// Dijkstra + dp
long long dist[10005][15]; // dist[i][j] = k:从 s 走到 i 且用了 j 次免费券后,最小花费为 k。
struct Node {
long long u, d, k; // 走到 u。最少走 d。使用 k 次免费。
bool operator <(const Node& b) const {
return b.d < d;
}
};
priority_queue<Node> q;
bool vis[10005][15];
void dijkstra() {
//memset(dist, LONG_LONG_MAX - 114514, sizeof(dist));
for (int i = 0; i <= 10002; i++) {
for (int j = 0; j <= 12; j++) {
dist[i][j] = LONG_LONG_MAX - 114514;
}
}
dist[s][0] = 0;
q.push((Node){s, 0, 0});
while (!q.empty()) {
long long u = q.top().u, d = q.top().d, k = q.top().k;
q.pop();
if (vis[u][k]) { // Important :是标记一个点的第某个状态(即拆成 k + 1 个点后的其中一个点。),而不是整个点!
continue;
}
vis[u][k] = 1; // Important :是标记一个点的第某个状态(即拆成 k + 1 个点后的其中一个点。),而不是整个点!
for (long long i = head[u]; i != 0; i = e[i].nex) {
long long v = e[i].v, w = e[i].w;
if (dist[u][k] + w < dist[v][k]) {
dist[v][k] = dist[u][k] + w;
q.push((Node){v, dist[v][k], k});
}
if (k <= K - 1 && dist[u][k] + 0 < dist[v][k + 1]) {
dist[v][k + 1] = dist[u][k] + 0;
q.push((Node){v, dist[v][k + 1], k + 1});
}
}
}
return ;
}
long long ans = LONG_LONG_MAX;
int main() {
//freopen("P4568.in", "r", stdin);
cin >> n >> m >> K;
cin >> s >> t;
for (long long i = 1; i <= m; i++) {
long long a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dijkstra();
//cout << dist[2][2] << "\n";
//cout << dist[t][min(m, K)] << "\n";
for (int i = 0; i <= K; i++) {
ans = min(ans, dist[t][i]);
}
cout << ans << "\n";
return 0;
}
```
by ZZQF5677 @ 2023-10-20 13:32:52