E. Rendez-vous de Marian et Robin - 题解

比赛与标签

比赛: Codeforces Round 974 (Div. 3) 标签: dfs and similar, graphs, shortest paths 难度: *1800

题目大意喵~

主人你好呀！这道题是关于一个浪漫的约会故事哦，喵~

故事的主角 Marian 和 Robin 分别在地图上的 1 号点（市场）和 n 号点（大橡树）完成了各自的事情，现在他们迫不及待地想要见面！

整个地图是一个由 n 个点和 m 条边组成的网络。每条边连接两个点，并且有一个通行时间 w。特别的是，地图上有 h 个点放着一匹马。

他们可以：

在点与点之间沿着边移动。
在任何一个有马的点，可以瞬间（花费0秒）骑上马。
一旦骑上马，之后所有的移动速度都会翻倍（也就是时间减半）。这个效果是永久的喵~
他们可以在任何一个点碰头，也可以在一个点上等待对方。

我们的任务就是，计算出他们俩能相遇的最早时间点。如果他们根本无法相遇（比如1号点和n号点不连通），就要输出 -1 的说。

解题思路分析喵~

喵哈哈，这道题的核心就在于“马”的存在呢！如果没有马，这就是一个非常经典的最短路问题。我们只需要分别从 1 号点和 n 号点跑两次 Dijkstra，得到他们各自到所有点的最短时间，然后遍历所有点作为会面点，计算出最小的会面时间就好啦。

但是！有了马，情况就变得有趣起来了。一个人在某个时刻的状态，不仅仅取决于他/她所在的位置，还取决于他/她是否骑着马。因为骑马会影响后续所有路径的耗时，对吧？

所以，我们可以把每个人的状态定义成一个二元组：(当前所在顶点 u, 是否骑马 has_horse)。其中 has_horse 可以是 0（没骑马）或 1（骑着马）。

这就像我们把原来的图复制了一份，变成了两层图，喵~

第0层（步行层）: 代表没有骑马时的状态。所有边的权重都是原始的 w。
第1层（骑行层）: 代表骑着马时的状态。所有边的权重都是 w / 2。

那么，状态之间是如何转换的呢？

层内移动:
- 在步行层，从点 u 到点 v，时间花费 w。这对应着状态 (u, 0) -> (v, 0)。
- 在骑行层，从点 u 到点 v，时间花费 w / 2。这对应着状态 (u, 0) -> (v, 1)。
层间转换（骑马）:
- 如果当前在点 u，并且这里有马 (is_horse[u] == true)，那么可以从步行状态切换到骑行状态。这个动作是瞬时的，花费时间为 0。这对应着一个从第0层到第1层的单向边：(u, 0) -> (u, 1)，权重为 0。
- 注意，一旦骑上马，就不能再下来了，所以没有从第1层回到第0层的边。

想清楚这个模型，问题就迎刃而解啦！我们可以用这个新的状态图来跑 Dijkstra 算法。

具体的步骤就是：

为 Marian 计算:
- 建立一个 dist_marian[i][state] 数组，表示 Marian 从 1 号点出发，到达点 i 时，处于 state 状态（0或1）的最短时间。
- 从初始状态 {cost: 0, u: 1, has_horse: 0} 开始跑 Dijkstra。
- 跑完之后，Marian 到达任意点 i 的最短时间就是 min(dist_marian[i][0], dist_marian[i][1])。
为 Robin 计算:
- 同样地，建立 dist_robin[i][state] 数组。
- 从初始状态 {cost: 0, u: n, has_horse: 0} 开始跑 Dijkstra。
- 跑完之后，Robin 到达任意点 i 的最短时间就是 min(dist_robin[i][0], dist_robin[i][1])。
寻找最佳会面点:
- 遍历所有点 i (从 1 到 n) 作为可能的会面点。
- 在点 i 的会面时间是 max(Marian到达i的最短时间, Robin到达i的最短时间)。
- 我们在所有这些会面时间里，取一个最小值，就是最终的答案啦！

如果最后找到的最小会面时间还是无穷大，那就说明他们永远也见不到了，真是个悲伤的故事呢，输出 -1 呜呜...

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>

// 为了让优先队列里的状态更清晰，我们用一个结构体来表示，喵~
struct State {
    long long cost;    // 到达当前状态的总花费
    int u;             // 当前所在的顶点
    int has_horse;     // 是否骑着马 (0: 没有, 1: 有)

    // 重载大于号，这样优先队列就是小顶堆啦
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

// 用一个常量来表示无穷大，方便得很~
const long long INF = std::numeric_limits<long long>::max();

// 这是一个为本题特殊改造过的 Dijkstra 算法
// 它计算从 start_node 出发到所有其他点的两种状态（骑马/不骑马）的最短路
std::vector<std::vector<long long>> dijkstra(int start_node, int n, const std::vector<std::vector<std::pair<int, int>>>& adj, const std::vector<bool>& is_horse) {
    // dist[i][0] 表示到顶点i且没骑马的最短时间
    // dist[i][1] 表示到顶点i且骑着马的最_短时间
    std::vector<std::vector<long long>> dist(n + 1, std::vector<long long>(2, INF));
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    // 初始状态：在起点，没骑马，花费为0
    dist[start_node][0] = 0;
    pq.push({0, start_node, 0});

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        long long d = current.cost;
        int u = current.u;
        int horse_state = current.has_horse;

        // 如果已经有更短的路径到达当前状态，就跳过，这是 Dijkstra 的优化
        if (d > dist[u][horse_state]) {
            continue;
        }

        // 状态转移 1: 沿着边移动到邻居顶点
        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            // 根据是否骑马，计算旅行时间
            long long travel_cost = (horse_state == 1) ? (long long)w / 2 : (long long)w;
            
            // 如果找到了更短的路径，就更新并加入队列
            if (dist[u][horse_state] != INF && dist[u][horse_state] + travel_cost < dist[v][horse_state]) {
                dist[v][horse_state] = dist[u][horse_state] + travel_cost;
                pq.push({dist[v][horse_state], v, horse_state});
            }
        }

        // 状态转移 2: 在当前点捡起一匹马 (如果可以的话)
        // 只有在没骑马(horse_state == 0)并且当前点有马的情况下才能发生
        if (horse_state == 0 && is_horse[u]) {
            // 从 "没骑马" 状态转移到 "骑着马" 状态，时间花费为0
            if (dist[u][0] != INF && dist[u][0] < dist[u][1]) {
                dist[u][1] = dist[u][0];
                pq.push({dist[u][1], u, 1});
            }
        }
    }
    return dist;
}

void solve() {
    int n, m, h;
    std::cin >> n >> m >> h;

    std::vector<bool> is_horse(n + 1, false);
    for (int i = 0; i < h; ++i) {
        int horse_v;
        std::cin >> horse_v;
        is_horse[horse_v] = true;
    }

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 为 Marian 计算从 1 号点出发的最短路
    auto dist_marian = dijkstra(1, n, adj, is_horse);
    
    // 为 Robin 计算从 n 号点出发的最短路
    auto dist_robin = dijkstra(n, n, adj, is_horse);

    // 对每个点 i，计算 Marian 和 Robin 到达它的最短时间
    std::vector<long long> t_marian(n + 1);
    std::vector<long long> t_robin(n + 1);
    for (int i = 1; i <= n; ++i) {
        // 到达点i的最短时间，就是骑马和不骑马两种情况的最小值
        t_marian[i] = std::min(dist_marian[i][0], dist_marian[i][1]);
        t_robin[i] = std::min(dist_robin[i][0], dist_robin[i][1]);
    }

    long long min_meeting_time = INF;
    // 遍历所有顶点作为可能的会面点
    for (int i = 1; i <= n; ++i) {
        // 必须两人都能到达这个点才行
        if (t_marian[i] != INF && t_robin[i] != INF) {
            // 会面时间取决于晚到的那个人
            min_meeting_time = std::min(min_meeting_time, std::max(t_marian[i], t_robin[i]));
        }
    }

    if (min_meeting_time == INF) {
        std::cout << -1 << "\n";
    } else {
        std::cout << min_meeting_time << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: O((M+H) log N) 的说。我们的状态图有 2*N 个节点（每个物理节点对应两个状态节点）和大约 2*M + H 条边（M条步行边，M条骑行边，H条捡马边）。Dijkstra 算法使用优先队列的复杂度是 O(E log V)，这里的 V 是状态数，E 是状态间的转移数。所以一次 Dijkstra 的复杂度是 O((M+H) log (2N))，也就是 O((M+H) log N)。我们跑了两次 Dijkstra，所以总时间复杂度还是这个量级。因为题目保证了 N 和 M 的总和，这个复杂度是完全可以通过的喵~
空间复杂度: O(N + M) 的说。我们需要存储邻接表 adj，它的大小是 O(N + M)。还需要存储距离数组 dist，它的大小是 O(2N)，也就是 O(N)。所以总的空间复杂度是 O(N + M)。

知识点与总结

喵~ 这道题真是个很好的练习呢！它教会了我们：

Dijkstra算法的灵活应用: 不要把 Dijkstra 看死板了，它不仅能解决点到点的最短路，还能解决状态到状态的最短路问题！
状态扩展/分层图思想: 这是解决这类带 "附加条件" 的最短路问题的关键！当一个点的状态不仅仅是它的位置时（比如本题的“是否骑马”，或者其他题的“剩余飞行次数”、“已使用道具种类”等），我们就可以把图分层，每一层代表一种附加状态。这样就把复杂的问题转化为了标准的最短路模型。
问题建模能力: 解题的第一步总是正确地理解问题并把它转化为我们熟悉的模型。把“骑马”这个行为理解成状态图中的一种特殊 0 权边，就是这道题的建模核心啦。

所以下次再遇到类似的最短路问题，如果发现有一些特殊的规则或者限制，不妨想一想，是不是可以用状态扩展/分层图的方法来解决呢？加油哦，主人！你一定可以的，喵~

E. Rendez-vous de Marian et Robin - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析喵~ ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​