洛谷 P12332 题解

本题为一道有约束的分层图最短路问题。

跟分层图最短路不一样的是，本题有一个连续 $k$ 短路不需要花费的一个约束条件，那么我们在传递状态的时候只需要特判一下，如果当前的已经使用了免费次数了，那么我们接下来我们松弛的时候就不需要花费。

这里我们使用一个二维数组 $dis_{i,k}$ 表示当前到达第 $i$ 个节点，使用了 $k$ 次免费次数的最短路径，那么我们可以得到状态转移方程：

不需要花费时：$dis_{v,{k-1}} = \min(dis_{v,{k-1}}, dis_{u,k})$。

需要花费时：$dis_{v,k} = \min(dis_{v,k}, dis_{u,k} + w)$。

C++ 代码如下：

#include <bits/stdc++.h>
using namespace std;const int maxn = 2000005;
const int inf = 1047483647;struct node {int to, next, data;
};node edge[maxn];
int head[maxn], cnt, k, n, m;void add_edge(int from, int to, int data) {edge[++cnt].to = to;edge[cnt].data = data;edge[cnt].next = head[from];head[from] = cnt;
}int dis[1005][15];
bool vis[1005][15];struct heap {int node, data, step;heap(int n, int d, int s) : node(n), data(d), step(s) {}bool operator>(const heap& h) const {return data > h.data;}
};void dijkstra() {memset(vis, 0, sizeof(vis));memset(dis, 0x3f, sizeof(dis));dis[0][k] = 0;priority_queue<heap, vector<heap>, greater<heap>> q;q.push(heap(0, 0, k));while (!q.empty()) {int now = q.top().node;int step = q.top().step;q.pop();if (vis[now][step])continue;vis[now][step] = true;for (int i = head[now]; i != 0; i = edge[i].next) {int to = edge[i].to, data = edge[i].data;if (step < k && step > 0 && dis[to][step - 1] > dis[now][step]) {dis[to][step - 1] = dis[now][step];q.push(heap(to, dis[to][step - 1], step - 1));}else if (step == k || step == 0) {if (dis[to][step] > dis[now][step] + data) {dis[to][step] = dis[now][step] + data;q.push(heap(to, dis[to][step], step));}if (step == k && dis[to][step - 1] > dis[now][step]) {dis[to][step - 1] = dis[now][step];q.push(heap(to, dis[to][step - 1], step - 1));}}}}
}int main() {cin >> n >> k >> m;while (m--) {int x, y, z;cin >> x >> y >> z;add_edge(x, y, z);add_edge(y, x, z);}dijkstra();cout << min(dis[n - 1][k], dis[n - 1][0]) << endl;return 0;
}