D. The way home - 题解

比赛与标签

比赛: Codeforces Round 857 (Div. 1) 标签: binary search, data structures, dp, graphs, greedy, shortest paths, sortings 难度: *2100

喵~ 题目讲了什么呀？

你好呀，我是乐于助人的猫娘！这道题目其实是一个很有趣的回家之旅呐~

我们扮演的魔法师布迪尼，在城市1被抢劫了，只剩下 p 个金币。他的家在城市 n。幸运的是，他可以在任何一个城市 i 进行表演来赚钱，每场表演能赚 w_i 个金币，表演次数不限！

整个国家有 m 条单向航线，每条航线从城市 a 到城市 b 需要花费 s 个金币。要坐飞机，我们的钱必须够数才行哦。

我们的目标是，用最少的总表演次数，成功从城市1回到城市 n。如果回不了家，就告诉我们这个坏消息，喵~

简单来说就是：

• 起点: 城市 1，有 p 金币。
• 终点: 城市 n。
• 目标: 最小化总表演次数。
• 行动:
  1. 在当前城市表演赚钱。
  2. 花钱乘坐飞机去另一个城市。

本猫娘的思考过程喵~

这道题呀，第一眼看上去就很像一个图论里的最短路问题，对吧？城市是图上的点，航班就是有向边。但是，边的“权重”是什么呢？是我们需要的表演次数，可这个次数不是固定的，它取决于我们到达一个城市时有多少钱，以及我们在哪里表演。这就有点复杂了呢。

为什么朴素的Dijkstra不行？

如果我们只把表演次数当作距离，用 dist[u] 表示到达城市 u 的最少表演次数，会遇到一个问题：

假设有两条路都能到达城市 u：

1. 表演了10次，到达时剩下100金币。
2. 表演了10次，到达时剩下500金币。

虽然表演次数相同，但第二种情况明显更优，因为它能让我们在后续的旅途中少表演几次！所以，我们的状态不仅要关心表演次数，还要关心剩余金币。

进化！带状态的Dijkstra

既然这样，我们就需要一个更丰富的状态来描述我们的处境。一个自然的想法是：dist[u] 存储到达城市 u 的 {最少表演次数, 最多剩余金币}。

但是，还有一个更关键的问题：我们在哪里表演赚钱最划算呢？

题目说“在城市 i，他可以组织表演...”，这似乎暗示我们只能在当前所在的城市表演。但仔细想想，如果我们需要一大笔钱来坐飞机，而当前城市的 w_i 很低，但我们之前经过了一个 w_j 很高的城市 j，我们最明智的选择是什么？当然是（概念上）回到城市 j 去表演啦！因为表演本身不消耗时间和其它成本，我们总可以利用上我们整个旅途已经解锁的最高赚钱效率！

这是一个非常重要的贪心思想！喵~ 也就是说，在任何需要用钱的时刻，我们都会用至今为止遇到过的最大的 w_i 来赚钱。

最终的解题思路！

基于这个贪心策略，我们的Dijkstra状态就清晰了！状态不仅仅是当前在哪座城市，还需要记录“至今为止解锁的最高赚钱效率”。

1. 状态定义: 我们定义一个状态为 (u, max_w_idx)，表示当前在城市 u，并且在从起点1到 u 的路径上，所经过的城市中赚钱效率最高的那个城市的“排名”是 max_w_idx。（我们预先把所有城市的 w_i 从大到小排个序，max_w_idx 就是这个排序后的索引）。
2. 距离数组: dist[u][max_w_idx] 存储一个 pair<long long, long long>，分别表示到达 (u, max_w_idx) 这个状态所需要的 {最少表演次数, 对应表演次数下的最大剩余金币}。
3. 优先队列: 使用优先队列（最小堆）来进行Dijkstra。队列中存储的元素是 State{perfs, money, u, max_w_idx}。我们优先选择 perfs 最小的，如果 perfs 相同，就选择 money 最多的（因为钱多不压身嘛~）。
4. 初始化:
   • 将所有城市的 w_i 从大到小排序，并记录每个城市的排名 w_rank。
   • dist 数组全部初始化为无穷大。
   • 将起点状态放入优先队列：{0, p, 1, w_rank[1]}。意思是，在城市1，表演0次，有p个金币，当前最高赚钱效率的城市就是城市1本身。
5. Dijkstra主循环:
   • 取出队首状态 current = {k, money, u, max_w_idx}。
   • 如果这个状态已经不是最优的了（即 dist[u][max_w_idx] 中记录的表演次数更少，或者次数相同但钱更多），就跳过它。
   • 如果 u 是终点 n，那么 k 就是我们找到的答案！可以直接返回啦。
   • 遍历从 u 出发的所有航班 (u, v, cost):
     • 计算需要的表演次数：当前赚钱效率是 W = rank_to_w[max_w_idx]。如果 money < cost，需要补足的钱是 cost - money，那么需要的表演次数就是 ceil((cost - money) / W)，用代码实现就是 (cost - money + W - 1) / W。
     • 计算新状态：
       • 总表演次数 next_k = k + needed_perfs。
       • 剩余金币 next_money = money + needed_perfs * W - cost。
       • 新的最高赚钱效率排名 next_max_w_idx = min(max_w_idx, w_rank[v])。因为到达了新城市 v，我们解锁的最高赚钱效率可能是 v 的，也可能是之前路径上的，取两者中效率更高的那个（也就是排名更靠前的那个）。
     • 如果新状态比 dist[v][next_max_w_idx] 更优，就更新 dist 并把新状态推入优先队列。

这样，我们就能找到到达城市 n 的最小表演次数了！如果队列空了还没到终点，那就是无解，输出-1。

来看代码实现吧！

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <tuple>

using namespace std;

// 用一个很大的数表示无穷大，喵~
const long long INF = 4e18; 

// Dijkstra中优先队列的状态结构体
struct State {
    long long perfs;    // 总表演次数
    long long money;    // 剩余金币
    int u;              // 当前所在城市
    int max_w_idx;      // 路径上遇到的最高w值的排名（索引）

    // 自定义比较函数，让优先队列变成最小堆
    // 优先按表演次数升序，次数相同则按金币降序
    bool operator>(const State& other) const {
        if (perfs != other.perfs) {
            return perfs > other.perfs;
        }
        return money < other.money;
    }
};

void solve() {
    int n;
    long long m, p;
    cin >> n >> m >> p;

    vector<long long> w(n + 1);
    vector<pair<long long, int>> w_sorted(n);
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        w_sorted[i - 1] = {w[i], i};
    }

    // 将城市的赚钱效率从高到低排序
    sort(w_sorted.rbegin(), w_sorted.rend());

    // 预处理，方便快速查找
    vector<int> w_rank(n + 1);       // 城市id -> 赚钱效率排名
    vector<int> rank_to_city(n);     // 排名 -> 城市id
    vector<long long> rank_to_w(n);  // 排名 -> 赚钱效率值
    for (int i = 0; i < n; ++i) {
        w_rank[w_sorted[i].second] = i;
        rank_to_city[i] = w_sorted[i].second;
        rank_to_w[i] = w_sorted[i].first;
    }

    // 邻接表存图
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, s;
        cin >> u >> v >> s;
        adj[u].push_back({v, s});
    }

    // 距离数组，dist[城市][最高w值排名] = {最少表演次数, 最多金币}
    vector<vector<pair<long long, long long>>> dist(n + 1, vector<pair<long long, long long>>(n, {INF, -1}));
    
    // 优先队列，用于Dijkstra
    priority_queue<State, vector<State>, greater<State>> pq;

    // 初始化起点状态
    int start_city = 1;
    int start_max_w_idx = w_rank[start_city];
    dist[start_city][start_max_w_idx] = {0, p};
    pq.push({0, p, start_city, start_max_w_idx});

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

        long long k = current.perfs;
        long long money = current.money;
        int u = current.u;
        int max_w_idx = current.max_w_idx;

        // 如果当前状态不是最优解，就跳过，喵~
        if (k > dist[u][max_w_idx].first || (k == dist[u][max_w_idx].first && money < dist[u][max_w_idx].second)) {
            continue;
        }

        // 到达终点啦！k就是答案！
        if (u == n) {
            cout << k << endl;
            return;
        }

        // 当前可用的最高赚钱效率
        long long current_w = rank_to_w[max_w_idx];

        // 遍历所有从u出发的航班
        for (const auto& edge : adj[u]) {
            int to = edge.first;
            int cost = edge.second;

            long long needed_perfs = 0;
            // 如果钱不够，就要表演赚钱
            if (money < cost) {
                long long money_needed = cost - money;
                // 向上取整的经典写法
                needed_perfs = (money_needed + current_w - 1) / current_w;
            }

            long long next_k = k + needed_perfs;
            long long next_money = money + needed_perfs * current_w - cost;
            
            // 到达新城市后，更新路径上的最高赚钱效率排名
            int next_max_w_idx = min(max_w_idx, w_rank[to]);

            // 松弛操作：如果找到了更优的路径
            if (dist[to][next_max_w_idx].first > next_k || 
               (dist[to][next_max_w_idx].first == next_k && dist[to][next_max_w_idx].second < next_money)) {
                dist[to][next_max_w_idx] = {next_k, next_money};
                pq.push({next_k, next_money, to, next_max_w_idx});
            }
        }
    }

    // 队列空了还没到终点，说明回不了家了QAQ
    cout << -1 << endl;
}

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

复杂度分析喵

• 时间复杂度: O(N * M * log(N)) 的说。 这里的状态数是 城市数 * 赚钱效率排名数，即 N * N。每条图的边 (u, v) 会对应 N 条状态图中的边（因为 max_w_idx 可以有 N 种取值）。所以状态图的边数是 O(N * M)。Dijkstra算法的复杂度是 O(E_state * log(V_state))，这里就是 O(N * M * log(N*N))，简化后是 O(N * M * log(N))。考虑到题目给的 N 和 M 的总和限制，这个复杂度是可以通过的。

• 空间复杂度: O(N * N) 的说。 主要是 dist 数组占用的空间，它的大小是 (N+1) * N，所以是 O(N^2)。

知识点与总结时间！

这道题真是一次有趣的冒险呢，它教会了我们几件重要的事情喵~

1. Dijkstra的灵活应用: 不要把Dijkstra想得太死板！它的核心是找到一个“最优”路径，这个“最优”可以是我们定义的任何东西。在这里，它是一个包含 (表演次数, 剩余金币) 的复合状态。
2. 状态设计是关键: 解决复杂图论问题的核心往往在于如何定义一个既能完整描述问题、又不会导致状态爆炸的状态。本题中，通过贪心策略，我们将“路径历史”压缩为“至今最高赚钱效率排名”这一单个维度，是解题的关键一步。
3. 贪心思想的力量: “总是在赚钱效率最高的已解锁城市表演”这个贪心选择，极大地简化了问题。在算法设计中，要时刻寻找可以贪心的地方！
4. 编程小技巧:
   • pair 和自定义的 struct 在优先队列中的使用非常方便。
   • 向上取整 (a + b - 1) / b 是一个需要牢记的实用小公式。
   • 处理多组测试用例时，记得每次都要清空和初始化数据结构哦。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问本猫娘哦！加油，你一定可以的，喵~ >w<