洛谷 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;
}