题目描述

在一个有 $N$ 座城市（编号 1 到 N）和 $M$ 条有向旅行线路的 $Z$ 省旅行。每条线路连接两座城市 $u$ 和 $v$，并且有两种可能的费用：$c$ 元现金或 $d$ 元旅游金。

$Z$ 省有一个旅游金计划：在城市 $i$，可以用 1 元现金兑换 $a_i$ 元旅游金（可以无限次兑换）。

森森计划从城市 1 出发，到达城市 $N$。他的旅行策略是：
1. 从城市 1 出发，使用现金支付路费，到达某个城市 $k$（$k$ 可以是 1 到 $N$ 中的任意一个城市）。
2. 在城市 $k$，将所有剩余的现金一次性兑换成旅游金，汇率是 $1:a_k$。
3. 从城市 $k$ 继续旅行到城市 $N$，这次只使用旅游金支付路费。
4. 特殊情况：他也可以选择全程使用现金（这相当于在终点 $N$ 进行“兑换”，但此时已不需要旅游金）。或者在起点 1 就进行兑换。

汇率 $a_i$ 可能会发生 $q$ 次调整。每次调整会改变某个城市 $x_i$ 的汇率 $a_{x_i}$ 为 $a_i’$。每次调整都是基于上一次调整后的结果。

你需要计算出，在每次汇率调整之后，森森为了完成他的旅行计划，最少需要准备多少初始现金。

样例

输入:
6 11 3
1 2 3 5
1 3 8 4
2 4 4 6
3 1 8 6
1 3 10 8
2 3 2 8
3 4 5 3
3 5 10 7
3 3 2 3
4 6 10 12
5 6 10 6
3 4 5 2 5 100
1 2
2 1
1 17

输出:

8
8
1

算法 (Dijkstra + 数据结构维护)

$O((N+M) \log N + Q \log N)$

思路分析

1. 分解问题: 森森的旅行计划可以分为两部分：

   • 第一部分：从城市 1 到某个中间城市 $k$，只使用现金支付。所需的最少现金是 1 到 $k$ 的现金最短路径成本。
   • 第二部分：从城市 $k$ 到城市 $N$，只使用旅游金支付。所需的最少旅游金是 $k$ 到 $N$ 的旅游金最短路径成本。
   • 在城市 $k$ 进行兑换：将第二部分所需的旅游金，通过城市 $k$ 的汇率 $a_k$ 折算成需要多少现金来兑换。

2. 计算最短路径:

   • 现金最短路径: 我们可以构建一个只包含现金费用的图。从源点 1 开始，使用 Dijkstra 算法计算到所有其他城市 $k$ 的最短路径距离。设 d_cash[k] 为从 1 到 $k$ 的最小现金花费。
   • 旅游金最短路径: 我们可以构建一个只包含旅游金费用的图。我们需要计算从每个城市 $k$ 到终点 $N$ 的最短路径。直接对每个 $k$ 跑 Dijkstra 太慢。一个常用的技巧是：在原图的反向图上，从终点 $N$ 开始跑 Dijkstra。设原图为 $G$，反向图为 $G_{rev}$（即将所有边的方向反转）。在 $G_{rev}$ 上从 $N$ 出发，使用旅游金费用进行 Dijkstra，得到的结果 dist[k] 就等于在原图 $G$ 上从 $k$ 到 $N$ 的最短旅游金花费。设 d_gold[k] 为从 $k$ 到 $N$ 的最小旅游金花费。

3. 计算总成本:
   假设森森选择在城市 $k$ 兑换旅游金。

   • 他需要携带 d_cash[k] 的现金用于第一部分的旅行。
   • 他需要 d_gold[k] 的旅游金用于第二部分的旅行。
   • 为了获得 d_gold[k] 的旅游金，在城市 $k$ 需要用现金兑换。需要的现金量是 $\lceil \frac{d\_gold[k]}{a_k} \rceil$。使用整数除法可以表示为 (d_gold[k] + a_k - 1) / a_k。
   • 因此，如果在城市 $k$ 兑换，总共需要的初始现金 $f(k)$ 为：
     $$f(k) = d\_cash[k] + \left\lceil \frac{d\_gold[k]}{a_k} \right\rceil = d\_cash[k] + \frac{d\_gold[k] + a_k - 1}{a_k}$$
   • 森森可以选择在任何一个城市 $k$ ($1 \le k \le N$) 进行兑换（包括起点 1 和终点 N）。我们需要找到使得 $f(k)$ 最小的那个 $k$。
   • 所以，对于一组给定的汇率 $a_1, \dots, a_n$，所需的最小初始现金是 $\min_{1 \le k \le N} \{ f(k) \}$。
   • 注意处理无穷大（INF）的情况：如果 d_cash[k] 或 d_gold[k] 是 INF，表示无法通过该城市 $k$ 完成计划，则 $f(k)$ 也应视为 INF。还需要注意计算 $f(k)$ 时加法可能导致的整数溢出。

4. 处理汇率更新:
   汇率会进行 $q$ 次更新。每次更新只改变一个城市的汇率 $a_x$。

   • 关键观察：d_cash 和 d_gold 数组的值不依赖于汇率 $a_k$，它们只取决于图的结构和边权（现金 c 和旅游金 d）。因此，我们只需要在程序开始时计算一次 d_cash 和 d_gold 即可。
   • 每次汇率更新 $(x, a’)$ 后，只有 $f(x)$ 的值可能发生改变，因为只有 $a_x$ 变了。其他所有 $f(k)$ ($k \ne x$) 的值保持不变。
   • 我们需要在每次更新后快速找到 $\min_{1 \le k \le N} \{ f(k) \}$。
   • 高效维护最小值: 我们可以使用一个数据结构来维护当前所有有效的 $f(k)$ 值（即非 INF 的值），并能快速查询最小值。std::multiset 非常适合这个任务。
     • 初始化: 计算初始汇率下的所有 $f(k)$。将所有有限的 $f(k)$ 值插入到 multiset<long long> costs 中。
     • 更新 $(x, a’)$:
       1. 获取更新前的 $f(x)$ 值（可以将其保存在一个数组 current_f 中）。
       2. 如果旧的 $f(x)$ 是有限的，从 costs 中删除一个旧的 $f(x)$ 值。（注意 multiset 可能包含重复值，要用 costs.erase(costs.find(old_f_x)) 来确保只删除一个）。
       3. 更新汇率 a[x] = a'。
       4. 重新计算新的 $f(x)$ 值。
       5. 更新 current_f[x] 为新的 $f(x)$。
       6. 如果新的 $f(x)$ 是有限的，将其插入到 costs 中。
       7. 查询并输出 costs 中的最小值，即 *costs.begin()。

5. 实现细节:

   • 图表示：使用邻接表 vector<vector<pair<int, i64>>>。需要两个图：adj_c (现金图) 和 adj_g_rev (反向旅游金图)。
   • Dijkstra：使用优先队列实现。注意处理 long long 和 INF 值，以及加法溢出。
   • 成本计算：calculate_f(k) 函数封装计算逻辑，包含 INF 和溢出检查。
   • 使用 multiset<i64> 存储 $f(k)$ 值。
   • 使用 vector<i64> 存储当前的 $f(k)$ 值 current_f，方便更新 multiset。

时间复杂度

• 预计算 Dijkstra: 两次 Dijkstra 算法，每次复杂度为 $O((N+M) \log N)$ 或 $O(M + N \log N)$ 取决于优先队列实现。总共 $O((N+M) \log N)$。
• 初始化 f(k) 和 multiset: 计算 N 个 $f(k)$，每个 $O(1)$。插入 multiset，每次 $O(\log N)$。总共 $O(N \log N)$。
• 处理 q 次更新: 每次更新：计算 $f(x)$ (O(1))，从 multiset 删除 (O(log N))，向 multiset 插入 (O(log N))，查询最小值 (O(1))。总共 $O(Q \log N)$。
• 整体复杂度: $O((N+M) \log N + Q \log N)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;

// 定义类型别名
using i64 = long long;
using u64 = unsigned long long; // 未使用
using u32 = unsigned; // 未使用

// 定义无穷大常量，使用 long long 最大值的三分之一防止加法溢出
const i64 INF = numeric_limits<i64>::max() / 3;

int main() {
    // 加速 IO
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q; // 城市数, 线路数, 调整次数
    std::cin >> n >> m >> q;

    // 构建邻接表：adj_c 存储现金图，adj_g_rev 存储反向的旅游金图
    // pair<int, i64> 存储 {邻接点, 边权}
    vector<vector<pair<int, i64>>> adj_c(n + 1);
    vector<vector<pair<int, i64>>> adj_g_rev(n + 1); // g for gold, rev for reversed

    // 读取 m 条线路信息
    for (int i = 0; i < m; ++i) {
        int u, v;
        i64 c, d; // 现金费用 c, 旅游金费用 d
        std::cin >> u >> v >> c >> d;
        adj_c[u].push_back({v, c});       // 添加现金图的边 u -> v, 权重 c
        adj_g_rev[v].push_back({u, d});   // 添加反向旅游金图的边 v -> u, 权重 d
    }

    // Dijkstra 算法模板 (lambda 表达式)
    // 输入: 图的邻接表, 起点
    // 输出: 从起点到所有点的最短距离 vector<i64>
    auto dijkstra = [&](const vector<vector<pair<int, i64>>>& graph, int start_node) {
        vector<i64> dist(n + 1, INF); // 初始化距离为 INF
        dist[start_node] = 0; // 起点距离为 0
        // 优先队列存储 {距离, 节点}，按距离从小到大排序
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
        pq.push({0, start_node});

        while (!pq.empty()) {
            auto [d, u] = pq.top(); // 取出当前距离最小的节点
            pq.pop();

            // 如果取出的距离 d 比已记录的 dist[u] 大，说明是旧的、无效的条目，跳过
            if (d > dist[u]) continue;

            // 遍历节点 u 的所有出边
            for (auto& edge : graph[u]) {
                int v = edge.first;       // 邻接点
                i64 weight = edge.second; // 边权

                // 松弛操作：检查是否可以通过 u 到达 v 来更新 dist[v]
                // 需要检查加法溢出: dist[u] + weight 是否会超过 INF
                // dist[u] < INF - weight 是一个安全的检查方式
                if (dist[u] != INF && weight != INF && dist[u] < INF - weight) {
                     if (dist[u] + weight < dist[v]) { // 如果找到了更短的路径
                         dist[v] = dist[u] + weight; // 更新距离
                         pq.push({dist[v], v});     // 将更新后的 {距离, 节点} 加入优先队列
                     }
                }
                // 下面的 else if 看起来是多余的或不完整，安全检查已经覆盖了必要情况
                // else if (dist[u] != INF && weight == INF && dist[v] == INF) {
                // }
            }
        }
        return dist; // 返回所有最短距离
    };

    // 预计算最短路径
    // d_cash[k]: 从 1 到 k 的最短现金路径
    vector<i64> d_cash = dijkstra(adj_c, 1);
    // d_gold[k]: 从 k 到 n 的最短旅游金路径 (通过在反向图上从 n 出发计算)
    vector<i64> d_gold = dijkstra(adj_g_rev, n);

    // 存储每个城市的汇率 a[k]
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }

    // 使用 multiset 存储所有当前有效的 f(k) 值，自动排序且允许重复
    multiset<i64> costs;
    // current_f[k] 存储当前汇率下计算出的 f(k) 值
    vector<i64> current_f(n + 1);

    // 计算 f(k) 的函数
    auto calculate_f = [&](int k) -> i64 {
        // 如果无法到达 k (现金) 或无法从 k 到达 n (旅游金)，则此路径无效
        if (d_cash[k] == INF || d_gold[k] == INF) {
            return INF;
        }
        i64 gold_cost = d_gold[k]; // 需要的旅游金
        i64 rate = a[k];         // 城市 k 的汇率
        // 计算兑换 gold_cost 旅游金所需的现金 (向上取整)
        i64 cash_for_gold = (gold_cost + rate - 1) / rate;

        // 检查 d_cash[k] + cash_for_gold 是否溢出
        if (d_cash[k] > INF - cash_for_gold) {
             return INF;
        }
        // 返回总的初始现金需求
        return d_cash[k] + cash_for_gold;
    };

    // 初始化：计算所有初始的 f(k) 并存入 multiset 和 current_f
    for (int k = 1; k <= n; ++k) {
        current_f[k] = calculate_f(k);
        if (current_f[k] != INF) { // 只存储有效的成本
            costs.insert(current_f[k]);
        }
    }

    // 处理 q 次汇率调整
    for (int i = 0; i < q; ++i) {
        int x;      // 被调整汇率的城市
        i64 new_a;  // 新的汇率
        std::cin >> x >> new_a;

        // 1. 从 multiset 中移除旧的 f(x) 值（如果存在且有效）
        if (current_f[x] != INF) {
            auto it = costs.find(current_f[x]); // 找到旧值的位置
            // 必须检查 find 是否成功，因为 erase(value) 会移除所有等于 value 的元素
            // 而 erase(iterator) 只移除迭代器指向的元素
            if (it != costs.end()) {
                 costs.erase(it); // 使用迭代器删除，确保只删一个
            }
        }

        // 2. 更新汇率 a[x]
        a[x] = new_a;
        // 3. 重新计算 f(x)
        current_f[x] = calculate_f(x);

        // 4. 将新的 f(x) 值插入 multiset（如果有效）
        if (current_f[x] != INF) {
            costs.insert(current_f[x]);
        }

        // 5. 输出当前 multiset 中的最小值 (即调整后的最低成本)
        // 题目保证一定有解，所以 costs 不会为空
        std::cout << *costs.begin() << "\n";
    }

    return 0; // 程序正常结束
}