马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
标题链接：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 ExRoc
- freopen("test.txt", "r", stdin);
- #endif // ExRoc
- ios::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;
- }
|
