Moe's CF Life

Appearance

G. Reducing Delivery Cost - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 677 (Div. 3) 标签: brute force, graphs, shortest paths 难度: *2100

喵喵的任务书~ ​

主人，你好呀！这次的任务是帮助 Berlyatov 市的市长优化快递路线，真是个有爱心的任务呢，喵~

这个城市有 n 个区和 m 条双向道路，每条路都有一定的通行成本。城市里还有 k 条快递路线，每条路线都连接着一个起点 a 和一个终点 b。聪明的快递员总是会选择成本最低的路径来送货。

我们被赋予了一项特殊的能力：可以选择最多一条道路，将它的通行成本变为 0！我们的目标是，通过明智地选择要免费的道路（或者选择不免费任何道路），让所有 k 条快递路线的总成本之和达到最小。

简单来说，就是要找到一个最优决策，让 Σ d(a_i, b_i) 最小，其中 d(x,y) 是 x 到 y 的最短路径成本，喵~

如何成为最优市长喵？ ​

呜哇，要考虑每一条路都变成 0 的情况，听起来好复杂！但是别担心，跟着本猫娘的思路，一步一步就能解开谜题啦！

如果我们直接去暴力枚举，会发生什么呢？ 我们可以尝试把 m 条边中的每一条边的权重都设为 0，然后对于每一种情况，都重新计算所有 k 条路线的最短路。这需要 m次枚举，每次枚举后都要为 k 条路线计算最短路。如果用 Dijkstra，一次最短路是 O(m log n)，那总复杂度就是 O(m * k * m log n)，这对于题目给的数据范围来说，肯定会超时的说！

所以，我们需要一个更聪明的办法，喵~

关键点在于，我们不需要每次都重新计算所有东西！我们可以先做一些预处理，把有用的信息都准备好。

Step 1: 预计算所有点对的最短路！ ​

无论我们让哪条边免费，原始的路径信息总是非常有用的。所以，我们第一步就应该计算出在原图中，任意两个点之间的最短路径长度。

这不就是“全源最短路”（All-Pairs Shortest Path, APSP）嘛！对于这道题，因为所有边的权重都是正数，我们可以从每个节点 i 出发，跑一次 Dijkstra 算法，来计算出它到所有其他节点 j 的最短距离。我们将结果保存在一个二维数组 dist[i][j] 中。

这样，我们就拥有了一张完整的城市交通成本地图啦！

Step 2: 思考“免费”边带来的变化 ​

现在，假设我们选择了一条连接 u 和 v 的边，把它变成免费的。对于一条从 a 到 b 的快递路线，它的最短路径会怎么变呢？

新的最短路径有以下几种可能，我们要从中选出最便宜的一种：

  1. 还是走老路：完全不经过我们新设置的免费边 (u, v)。它的成本就是我们预计算好的 dist[a][b]。
  2. 从 u 到 v 利用免费边：快递员可以先从 a 走到 u，然后免费地从 u 走到 v，最后再从 v 走到 b。这条新路径的总成本就是 dist[a][u] + 0 + dist[v][b]。
  3. 从 v 到 u 利用免费边：同理，也可以从 a 走到 v，免费地从 v 走到 u，再从 u 走到 b。成本是 dist[a][v] + 0 + dist[u][b]。

所以，当边 (u, v) 免费后，从 a 到 b 的新最短路径成本就是： min(dist[a][b], dist[a][u] + dist[v][b], dist[a][v] + dist[u][b])

Step 3: 枚举所有边，找到最优解！ ​

有了上面的分析，我们的策略就清晰多啦！

  1. 首先，用 n 次 Dijkstra 算法预计算出 dist[i][j]。
  2. 计算一个初始的总成本 base_total，也就是不使用任何免费边时，所有 k 条路线的成本总和。这个值是我们的一个候选答案。
  3. 然后，我们遍历 m 条边中的每一条边 (u, v)。
  4. 对于每一条被选作免费的边，我们再遍历所有 k 条快递路线 (a, b)，利用上面的公式计算出每条路线的新最短路径成本，并把它们加起来得到一个 current_total。
  5. 用 current_total 和我们记录的全局最小总成本 best_total 比较，如果 current_total 更小，就更新 best_total。
  6. 遍历完所有 m 条边后，best_total 就是我们能得到的最小总成本啦！

这个方法通过预处理大大减少了重复计算，变得非常高效，可以顺利通过了喵！

魔法代码咏唱！ ​

下面就是实现这个思路的魔法代码，本猫娘加上了详细的注释，方便主人理解哦~

cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;
typedef long long ll;
const ll INF = 1e18; // 用一个很大的数表示无穷远，喵~

int main() {
    // 关掉同步流，让输入输出快一点，nya~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    // 用邻接表存图，同时用一个 vector 存下所有的边，方便后面枚举
    vector<vector<pair<int, int>>> graph(n);
    vector<tuple<int, int, int>> edges;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 题目节点从1开始，我们转成从0开始方便处理
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
        edges.emplace_back(u, v, w);
    }

    // 喵~ 先把所有点对之间的最短路算出来！这就是我们的预处理步骤
    vector<vector<ll>> dist(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) {
        // 用 Dijkstra 算法，从每个点 i 出发，求到所有其他点的最短路
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        pq.push({0, i});
        dist[i][i] = 0;

        while (!pq.empty()) {
            auto [d_val, u] = pq.top();
            pq.pop();

            // 这是一个小优化，如果当前取出的路径长度已经不是最短的了，就跳过，喵~
            if (d_val != dist[i][u]) continue;

            for (auto [v, w] : graph[u]) {
                // 松弛操作：如果找到了更短的路，就更新一下然后放进优先队列里~
                if (dist[i][v] > dist[i][u] + w) {
                    dist[i][v] = dist[i][u] + w;
                    pq.push({dist[i][v], v});
                }
            }
        }
    }

    // 记录 k 条快递路线
    vector<pair<int, int>> routes;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        routes.emplace_back(a, b);
    }

    // 记录一下最开始，什么都不做时的总成本
    ll base_total = 0;
    for (auto [a, b] : routes) {
        base_total += dist[a][b];
    }

    ll best_total = base_total; // 初始化最优解为原始总成本

    // 现在，我们来试试把每一条边变成 0 会怎么样~
    for (auto [u, v, w] : edges) {
        ll total = 0;
        // 对于每条送货路线 (a, b)
        for (auto [a, b] : routes) {
            // 选项1：a -> u ->(免费)-> v -> b
            ll option1 = dist[a][u] + dist[v][b];
            // 选项2：a -> v ->(免费)-> u -> b
            ll option2 = dist[a][v] + dist[u][b];
            // 新的最短路就是这三种情况里最便宜的那个！(原来的路 vs 两条新路)
            ll candidate = min(dist[a][b], min(option1, option2));
            total += candidate;
        }
        // 更新我们的全局最优解~
        if (total < best_total) {
            best_total = total;
        }
    }

    cout << best_total << '\n';

    return 0;
}

时空魔法消耗分析 ​

  • 时间复杂度: O(n * m log n + m * k) 的说

    • 预处理部分，我们对 n 个节点都跑了一遍 Dijkstra。每次 Dijkstra 的复杂度是 O(m log n)。所以这部分的复杂度是 O(n * m log n)。
    • 枚举部分，我们遍历了 m 条边，对于每条边，又遍历了 k 条路线。这部分的复杂度是 O(m * k)。
    • 总的来说，总时间复杂度就是两者之和，O(n * m log n + m * k)，对于这道题的限制来说是完全可以接受的！

  • 空间复杂度: O(n^2) 的说

    • 我们用了一个邻接表 graph 来存图，空间是 O(n + m)。
    • 最主要的空间开销是 dist 矩阵，用来存储所有点对之间的最短路，大小是 n x n，所以空间复杂度是 O(n^2)。

猫娘的私藏秘籍 ​

这次的任务是不是很有趣呀？我们来总结一下学到了什么吧，喵~

  1. 预处理 + 枚举思想：这是解决这类问题的经典套路！当直接暴力枚举的代价太高时，可以思考哪些信息是可以被重复利用的。通过一次性的“高成本”预处理（比如这里的全源最短路），来换取后续每次枚举时的“低成本”计算。

  2. 全源最短路 (APSP) 的选择：提到全源最短路，大家可能会想到 Floyd-Warshall 算法 (O(n^3))。但在边权为正的稀疏图（m 远小于 n^2）中，像本题这样跑 n 次 Dijkstra (O(n * m log n)) 会是更优的选择哦！

  3. 路径更新的思考方式：当图中只有一条边的权重发生变化时，新的最短路径只可能有两种情况：要么还是原来的最短路径，要么是包含了这条变化边的新路径。抓住这个核心，就能把复杂的问题简化！

希望这次的题解能帮到主人！多做图论题，你也能像本猫娘一样对最短路了如指掌的，加油喵！(ฅ'ω'ฅ)

Released under the MIT License.

Copyright © 2024-present Moe