M. Moving Both Hands - 题解

比赛与标签

比赛: COMPFEST 14 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred) 标签: dp, graphs, shortest paths 难度: *1800

题目大意喵~

主人，这道题是这样的呐：我们有一个包含 N 个点和 M 条边的有向图，每条边都有一个权值，代表通过它需要的时间。

游戏开始时，我们的左手放在 1 号点，右手放在 p 号点（p 会从 2 到 N 变化）。我们的任务是，通过不断移动其中一只手（一次只能动一只），最终让两只手在同一个点相遇。

我们需要对每一个可能的右手起始点 p（从 2 到 N），计算出让两只手相遇所需要的最小总时间。如果无论如何都无法相遇，就输出 -1 的说。

简单来说，就是对于每个 p ∈ [2, N]，求两只手从 (1, p) 出发，到达同一个终点 k 的最短总耗时。

解题思路的奇妙旅程！

这道题看起来有点复杂，要对每个 p 都算一次，但别怕，我们来把它拆解成可爱的小步骤，喵~

首先，我们来分析一下总时间是怎么计算的。假设我们决定让两只手在 k 号点相遇，那么总时间就是： 总时间 = (左手从 1 走到 k 的时间) + (右手从 p 走到 k 的时间)

用图论的语言来说，就是 dist(1, k) + dist(p, k)，其中 dist(u, v) 是从点 u到点 v 的最短路径长度。为了找到最快的方案，我们需要在所有可能的相遇点 k 中，找到一个能让这个总时间最小的点。

所以，对于每个给定的起始点 p，我们要计算的其实是： Ans(p) = min_{k=1..N} { dist(1, k) + dist(p, k) }

如果对每个 p 都去遍历所有的 k，并且每次都重新计算 dist(p, k)，那可就太慢啦，肯定会超时的说！(｡>ω<｡)

第一步：预处理公共部分

我们观察一下这个式子 dist(1, k) + dist(p, k)。dist(1, k) 这一项，其实和 p 是没有关系的！不管右手从哪里出发，左手从 1 号点到任意点 k 的最短路都是固定的。

所以，我们可以先用一次 Dijkstra 算法，计算出 1 号点到所有其他点的最短路。我们把这个距离数组记为 d1，d1[k] = dist(1, k)。这一步的时间复杂度是 O(M log N)，非常快！

现在，问题就变成了： Ans(p) = min_{k=1..N} { d1[k] + dist(p, k) }

第二步：反向思考的魔法！

现在问题是，对于每个 p，我们还是需要 dist(p, k)。难道真的要为每个 p 跑一次 Dijkstra 吗？当然不要！这里有个超级厉害的技巧——反向图！

在有向图中，从 p 走到 k 的最短路，和在反向图（把所有边的方向都反过来）上从 k 走到 p 的最短路是一样的！我们把反向图上的最短路记为 rev_dist，那么 dist(p, k) = rev_dist(k, p)。

于是，我们的公式又变身啦： Ans(p) = min_{k=1..N} { d1[k] + rev_dist(k, p) }

第三步：多源最短路的华丽变身！

主人请看，Ans(p) 的这个最终形态是不是很眼熟？d1[k] 可以看作是每个点 k 的一个“初始代价”，而 rev_dist(k, p) 是从 k 到 p 的路径成本。整个式子就是在求，从所有可能的“源点” k 出发，各自带着 d1[k] 的初始代价，在反向图上走到 p 的最小总代价！

这不就是一个多源最短路问题嘛！我们可以用一次 Dijkstra 算法来解决所有 p 的问题！

具体做法是：

建立一个反向图 rev。
初始化一个新的距离数组 final_dist，让 final_dist[k] = d1[k]。
创建一个优先队列，把所有可达的点 k（即 d1[k] 不是无穷大）和它的初始代价 d1[k] 一起放进去，即 pq.push({d1[k], k})。
在反向图上跑 Dijkstra！当从优先队列中取出 {cost, u} 时，对于 u 在反向图中的每条出边 u -> v（权重为 w），我们尝试用 cost + w 来更新 v 的距离。

当这个 Dijkstra 跑完后，final_dist[p] 数组里存的就是我们想要的 Ans(p) 啦！是不是超级巧妙的说？(＾▽＾)

总结一下我们的完美计划：

跑一次 Dijkstra，计算从 1 出发到所有点的最短路 d1。
在反向图上，以 d1 作为所有点的初始距离，跑一次多源 Dijkstra，得到最终答案。

代码实现喵~

cpp

// 完整的AC代码，添加详细注释解释关键逻辑
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    // 一个存正向图，一个存反向图，方便我们操作~
    vector<vector<pair<int, ll>>> orig(N + 1);
    vector<vector<pair<int, ll>>> rev(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        orig[u].push_back({v, w});
        rev[v].push_back({u, w}); // 同时构建反向图
    }

    const ll INF = 1e18; // 用一个超大的数表示无穷远，记得用 long long 哦！
    vector<ll> d1(N + 1, INF);
    d1[1] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 1});

    // 第一步！用 Dijkstra 跑一遍正向图，计算从 1 号点出发到所有点的最短路 d1
    while (!pq.empty()) {
        auto [cost, u] = pq.top();
        pq.pop();

        if (cost != d1[u]) continue; // 经典的 Dijkstra 优化，如果是旧的、更长的路径就不处理

        for (auto [v, w] : orig[u]) {
            ll new_cost = cost + w;
            if (new_cost < d1[v]) {
                d1[v] = new_cost;
                pq.push({new_cost, v});
            }
        }
    }

    // dist_rev 就是我们最终的答案数组，一开始就等于 d1，这就是我们说的'初始代价'呐
    vector<ll> dist_rev = d1;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq2;
    
    // 把所有可达的点（d1[i] 不是无穷大）作为多源 Dijkstra 的源点放进第二个优先队列 pq2
    for (int i = 1; i <= N; i++) {
        if (dist_rev[i] < INF) {
            pq2.push({dist_rev[i], i});
        }
    }

    // 第二步！在反向图上跑多源 Dijkstra
    while (!pq2.empty()) {
        auto [cost, u] = pq2.top();
        pq2.pop();

        if (cost != dist_rev[u]) continue;

        // 在反向图上进行松弛操作
        for (auto [v, w] : rev[u]) {
            ll new_cost = cost + w;
            if (new_cost < dist_rev[v]) {
                dist_rev[v] = new_cost;
                pq2.push({new_cost, v});
            }
        }
    }

    // 最后把算好的答案一个一个打印出来就好啦
    for (int i = 2; i <= N; i++) {
        if (dist_rev[i] >= INF) {
            cout << "-1"; // 如果是无穷大，就说明到不了，输出-1喵~
        } else {
            cout << dist_rev[i];
        }
        if (i < N) cout << " ";
    }
    cout << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(M log N) 的说。我们总共运行了两次 Dijkstra 算法。每一次的复杂度都是 O(M log N)（在使用优先队列的情况下），所以总的时间复杂度就是 O(M log N) 啦，非常高效！
空间复杂度: O(N + M) 的说。我们用邻接表来存储正向图和反向图，占用了 O(N + M) 的空间。此外还有几个大小为 N 的距离数组，所以总的空间复杂度是 O(N + M)。

知识点与总结

这道题真的非常有趣，把好几个知识点巧妙地融合在了一起呢，喵~

Dijkstra 算法: 这是解决单源最短路问题的经典算法，也是本题的基础。主人一定要熟练掌握它哦！
反向图思想: 这是一个非常强大的图论技巧！当遇到需要处理“到某个点的路径”时，可以尝试将其转化为反向图上“从某个点出发的路径”，从而简化问题。
多源最短路: 本题最核心的转化就是将问题建模成了一个多源最短路问题。通过给每个点赋一个初始代价，然后跑一次 Dijkstra，就能同时求出所有目标点的答案。这种思想非常值得学习！
问题转化能力: 从复杂的题目描述中提炼出数学模型 min{dist(1,k) + dist(p,k)}，再一步步优化和变形，最终找到高效的解法，这是算法竞赛中非常重要的能力呐！

希望本猫娘的讲解能帮助到主人！如果还有不明白的地方，随时可以再来问我哦~ 加油喵！(๑•̀ㅂ•́)و✧

M. Moving Both Hands - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路的奇妙旅程！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​