题目链接：https://www.lanqiao.cn/problems/3542/learning/
个人评价：难度 3 星（满星：5）
前置知识：迪杰斯特拉
整体思路
- 这类题目的套路解法是把每一种状态都定义为图上的一个点，用迪杰斯特拉计算初始状态到每一点的最短距离，通过状态之间的合法转移来计算状态状态之间的距离；
- 每一种状态由“节点编号”与“已选择免伤害边数”决定，定义 d i s [ p o s ] [ k ] dis[pos][k] dis[pos][k] 表示从状态 d i s [ 0 ] [ 0 ] dis[0][0] dis[0][0] 转移到节点 p o s pos pos，已选择 k k k 条免伤害边，则状态之间的距离有如下计算方式：
d i s [ p o s ] [ k ] = { min ( d i s [ p r e i ] [ 0 ] + w p r e i − p o s ) k = 0 o r k = K min ( d i s [ p r e i ] [ k − 1 ] ) o t h e r s dis[pos][k]= \begin{cases} \min(dis[pre_i][0]+w_{pre_i-pos}) & k=0~or~k=K\\ \min(dis[pre_i][k-1]) & others \end{cases} dis[pos][k]={min(dis[prei][0]+wprei−pos)min(dis[prei][k−1])k=0 or k=Kothers
- 其中 p r e i pre_i prei 表示节点 p o s pos pos 在迪杰斯特拉过程中的第 i i i 个前置节点编号； w p r e i − p o s w_{pre_i-pos} wprei−pos 表示从节点 p r e i pre_i prei 到节点 p o s pos pos 的距离 w w w 的值；
- 当 k = 0 k=0 k=0 时的递推，即完全不使用魔法，最一般的迪杰斯特拉写法；
- 当 k < K k<K k<K 时的递推，表示到当前节点连续选择 k k k 条边的最短距离等于从前置节点往前连续选择 k − 1 k-1 k−1 条边的距离；
- 当 k = K k=K k=K 时的递推，表示之前某个时刻已经选好连续的 K K K 条边了，后续无法再选择新的边，此时用一般的迪杰斯特拉递推写法即可；
- 由于从起点到终点可能不到 K K K 条边，或者不使用魔法的距离更短，所以最终答案为 min ( d i s [ N − 1 ] [ K ] , d i s [ N − 1 ] [ 0 ] ) \min(dis[N-1][K],dis[N-1][0]) min(dis[N−1][K],dis[N−1][0])。
过题代码
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int maxn = 1000 + 100;
struct Node {int pos, k, dis;Node() {}Node(int pos, int k, int dis) : pos(pos), k(k), dis(dis) {}
};bool operator<(const Node &a, const Node &b) {return a.dis > b.dis;
}int n, k, m, u, v, w;
vector<Node> G[maxn];
priority_queue<Node> que;
int dis[maxn][100];
bool vis[maxn][100];int main() {
#ifdef ExRocfreopen("test.txt", "r", stdin);
#endif // ExRocios::sync_with_stdio(false);cin >> n >> k >> m;for (int i = 0; i < m; ++i) {cin >> u >> v >> w;G[u].push_back(Node(v, 0, w));G[v].push_back(Node(u, 0, w));}memset(dis, 0x3f, sizeof(dis));que.push(Node(0, 0, 0));dis[0][0] = 0;while (!que.empty()) {Node tmp = que.top();que.pop();if (vis[tmp.pos][tmp.k]) {continue;}vis[tmp.pos][tmp.k] = true;for (Node &node: G[tmp.pos]) {// k == 0 表示不使用魔法，k == K 表示已使用过魔法if (tmp.k == 0 || tmp.k == k) {if (dis[node.pos][tmp.k] > dis[tmp.pos][tmp.k] + node.dis) {dis[node.pos][tmp.k] = dis[tmp.pos][tmp.k] + node.dis;que.push(Node(node.pos, tmp.k, dis[node.pos][tmp.k]));}}// 当 k < K 时，不能不使用魔法，所以只能直接取等号if (tmp.k < k) {if (dis[node.pos][tmp.k + 1] > dis[tmp.pos][tmp.k]) {dis[node.pos][tmp.k + 1] = dis[tmp.pos][tmp.k];que.push(Node(node.pos, tmp.k + 1, dis[node.pos][tmp.k + 1]));}}}}cout << min(dis[n - 1][0], dis[n - 1][k]) << endl;return 0;
}
