题解：P6029 [JSOI2010] 旅行

five_rice_water · 2025-03-21 13:53:00 · 题解

洛谷P6029 题解

本人过的第一道黑题，也是本人在洛谷的第 1000 道题。

这题其实不是很难，个人感觉到不了黑。

题意简述

对于一个有 n 个点，m 条边的无向图，可以交换 k 对边的边权，问交换完的图上从 1 号点到 n 号点的最短路是多少。

思路

我们先来考虑和本题的思路部分很像的这样一道题：

现在有一个序列 a，可以交换任意两个数字 k 次，问操作完之后的序列的最大子段和。数据保证 1 \le n \le 500。

不难发现，当 k 过大的时候，这个问题没有意义。但是当 k 相对小的时候，我们就要思考做法了。

一种相对可行的解法是这样的，我们枚举最终最大子段和所在的区间左右端点，再去考虑往这个区间里面交换前 k 大的数字。

当然要考虑前 k 大的数字有一部分已经在这个区间里面了，所以细节处理会麻烦一点，但总之是 O(n^3) 左右可以解决的问题，不过该时间复杂度下对应数据范围可能会超时，但这不是我们这篇题解的核心内容，所以暂时不提。

总结一下，我们用到的思路是枚举终态，也就是考虑最终的答案可能来自哪些部分，然后进一步操作。

再简单一点，就是找一些能概括所有状态的情况，然后依次枚举所有情况，找到在该种情况的最优解，最后得到最终的最优解。

那么放到这道题上，到底哪些状态是有限可以被枚举同时可以概括所有情况的呢？

一种可行的情况是这张图上前 p 短的边是否在从 1 到 n 的路径上。

这样枚举，可以概括所有的情况。

代码实现

第一步，我们要枚举 p，然后跑最短路。

但是我们已经知道了前 p 短的路径了，有什么用呢？

我们可以用 dp 去获得“前 p 短的路都在 1 到 n 的路径上时的最优解”。

怎么定义状态呢？我们设 f_{i,j,t} 表示走过了 j 条原本就是前 p 短的边，并且使用了 t 次魔法后，从 1 走到 i 的最小代价（不计算前 p 短的边的长度）。

怎么转移呢？有以下两种情况。

当 t+1\le k 时，可以尝试在 x 到 v 的路径上使用一次魔法，因为交换过来的边一定是前 p 短的边的其中一根（否则答案一定不会更优），所以不记录答案，即更新 f_{v,j,t+1} 的值为 f_{x,j,t}。

另外，当这条边是我们枚举的前 p 条边中的其中一条时，因为是前 p 短的边，所以不记录答案，我们可以更新 f_{v,j+1,t} 的值为 f_{x,j,t}。

否则，这条边要计算到答案里，更新 f_{v,j,t} 的值为 f_{x,j,t} + w。

最后，从 1 到 n，走了 j 条原本就是前 p 小长度的边，用了 k 次魔法的最小代价应该是 f_{n,j,t} + sum_p。其中 sum_p 表示前 p 小的边的长度和。

最后加上 sum_p 的原因是在进行 dp 的过程中，不方便计算魔法交换过来的边的边权。

最后的答案就是所有 j+t \le p 的 f_{n,j,t}+sum_p 的最小值（因为超过范围的没有意义）。

代码展示

代码实现时注意一下边界处理，例如下面的 j+1<=m。

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const int M = 155;
int n, m, k;

struct graph {
    int v, w, id;
};
vector<graph>e[N];

struct node {
    int x, j, k, dis;
    friend bool operator <(node a, node b) {
        return a.dis > b.dis;
    }
};

struct edge {
    int w, id;
} E[M];

bool cmp(edge a, edge b) {
    return a.w < b.w;
}
int mp[M], f[N][M][M], vis[N][M][M];

void dijkstra(int check) {
    memset(f, 0x3f, sizeof(f));
    memset(vis, 0, sizeof(vis));
    f[1][0][0] = 0;
    priority_queue<node>q;
    q.push({1, 0, 0, 0});
    while (!q.empty()) {
        node tmp = q.top();
        q.pop();
        int x = tmp.x;
        int j = tmp.j;
        int k_ = tmp.k;
        if (vis[x][j][k_])
            continue;
        vis[x][j][k_] = 1;
        for (int i = 0; i < e[x].size(); i++) {
            int v = e[x][i].v;
            int w = e[x][i].w;
            int id = e[x][i].id;
            if (k_ + 1 <= k && f[v][j][k_ + 1] > f[x][j][k_]) {
                f[v][j][k_ + 1] = f[x][j][k_];
                q.push({v, j, k_ + 1, f[v][j][k_ + 1]});
            }
            if (mp[id] <= check) {
                if (j + 1 <= m && f[v][j + 1][k_] > f[x][j][k_]) {
                    f[v][j + 1][k_] = f[x][j][k_];
                    q.push({v, j + 1, k_, f[v][j + 1][k_]});
                }
            } else {
                if (f[v][j][k_] > f[x][j][k_] + w) {
                    f[v][j][k_] = f[x][j][k_] + w;
                    q.push({v, j, k_, f[v][j][k_]});
                }
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        e[x].push_back({y, z, i});
        e[y].push_back({x, z, i});
        E[i] = {z, i};
    }
    sort(E + 1, E + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        mp[E[i].id] = i;
    }
    int sum = 0;
    int ans = INT_MAX;
    for (int i = 0; i <= m; i++) {
        sum += E[i].w;
        dijkstra(i);
        for (int j = 0; j <= i; j++) {
            for (int K = 0; K <= k; K++) {
                if (j + K <= i) {
                    ans = min(ans, f[n][j][K] + sum);
                } else
                    break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}