結果

問題 No.3111 Toll Optimization
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 13:01:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 233 ms / 5,000 ms
コード長 6,768 bytes
コンパイル時間 1,121 ms
コンパイル使用メモリ 93,740 KB
実行使用メモリ 19,780 KB
最終ジャッジ日時 2025-04-19 13:01:45
合計ジャッジ時間 8,830 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // 用于输入输出流
#include <vector>   // 用于动态数组 (vector)
#include <queue>    // 用于优先队列
#include <tuple>    // 用于将多个值存储在一起 (优先队列中的状态)
#include <limits>   // 用于 numeric_limits 获取无穷大值
#include <algorithm> // 用于 min 函数

using namespace std;

// 定义一个大的常量来表示无穷大。
// 使用 long long 最大值的一半以防止加法溢出。
// 这样做是因为图中路径的成本可能累加得很大，但应该小于 INF。
// 如果一条路径的成本达到或超过 INF，我们将其视为不可达或非常昂贵。
const long long INF = numeric_limits<long long>::max() / 2;

int main() {
    // 优化 C++ 标准库的输入输出操作，使其更快。
    ios_base::sync_with_stdio(false); // 关闭 C 和 C++ 标准流的同步
    cin.tie(NULL); // 解除 cin 和 cout 的绑定

    int n; // 城镇数量 (Number of towns)
    int m; // 桥的数量 (Number of bridges)
    int k; // 优惠券数量 (Number of coupons)
    cin >> n >> m >> k;

    // 读取 M 座桥的费用，存储在 vector 中。
    vector<long long> costs(m);
    for (int i = 0; i < m; ++i) {
        cin >> costs[i];
    }

    // 图的邻接表表示法。
    // adj[i] 是一个 vector，存储与城镇 i 相连的所有边。
    // 每个边表示为一个 pair：{邻居城镇, 桥费用}。
    vector<vector<pair<int, long long>>> adj(n + 1); // 大小为 n+1，因为城镇编号从 1 到 n
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // 由于桥是双向的，我们需要在邻接表中为两个方向都添加边。
        // 使用第 i 座桥的费用 costs[i]。
        adj[u].push_back({v, costs[i]});
        adj[v].push_back({u, costs[i]});
    }

    // 距离数组：dist[town][coupons_used] 存储到达 'town'
    // 且恰好使用了 'coupons_used' 张优惠券的最小费用。
    // 初始化所有距离为无穷大 INF。
    // 大小为 (n+1) x (k+1)。
    vector<vector<long long>> dist(n + 1, vector<long long>(k + 1, INF));

    // 用于 Dijkstra 算法的优先队列。
    // 存储元组 {费用, 城镇, 已用优惠券数}。
    // `greater<tuple<...>>` 使其成为最小优先队列（费用最低的元素优先出队）。
    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<tuple<long long, int, int>>> pq;

    // 起始状态：我们在城镇 1，没有使用任何优惠券（0 张），初始费用为 0。
    dist[1][0] = 0;
    pq.push({0, 1, 0}); // 将起始状态 {cost=0, town=1, coupons_used=0} 推入优先队列。

    // Dijkstra 算法主循环，直到优先队列为空。
    while (!pq.empty()) {
        // 从优先队列中获取费用最小的状态（节点）。
        // 使用 C++17 结构化绑定 (structured binding) 来方便地解包元组。
        auto [current_cost, u, coupons_used] = pq.top();
        pq.pop(); // 从队列中移除该状态。

        // 延迟删除/有效性检查：
        // 如果我们从队列中取出的状态的费用 (current_cost) 大于
        // 我们已经记录的到达该状态 (u, coupons_used) 的最小费用 (dist[u][coupons_used])，
        // 这意味着我们找到了一个更短的路径到达 (u, coupons_used) 并且已经处理过它。
        // 当前这个条目是过时的（或者说是多余的），可以直接跳过。
        if (current_cost > dist[u][coupons_used]) {
            continue;
        }

        // 探索当前城镇 'u' 的所有邻居 'v'。
        // `auto& edge` 用于迭代 `adj[u]` 中的每个 `pair<int, long long>`。
        for (auto& edge : adj[u]) {
            int v = edge.first;         // 邻居城镇的编号。
            long long bridge_cost = edge.second; // 连接 u 和 v 的桥的费用。

            // 考虑两种移动方式：

            // 选择 1：不使用优惠券过桥
            // 计算通过这座桥到达邻居 'v' 的新费用。
            // 新费用 = 到达当前城镇 u 的费用 + 桥的费用。
            // 到达的状态是 (v, coupons_used)，使用的优惠券数量不变。
            long long cost_without_coupon = dist[u][coupons_used] + bridge_cost;
            // 如果这条路径比当前已知的到达状态 (v, coupons_used) 的最短路径更便宜：
            if (cost_without_coupon < dist[v][coupons_used]) {
                // 更新到达状态 (v, coupons_used) 的最小费用。
                dist[v][coupons_used] = cost_without_coupon;
                // 将这个改进后的状态（或新发现的状态）添加到优先队列中。
                pq.push({dist[v][coupons_used], v, coupons_used});
            }

            // 选择 2：使用优惠券过桥（仅当还有优惠券可用时）
            // 检查是否还有优惠券可用 (coupons_used < k)。
            if (coupons_used < k) {
                // 使用优惠券时，这座桥的费用变为 0。
                // 到达邻居 'v' 的总费用等于到达当前城镇 'u' 的费用。
                // 到达的状态是 (v, coupons_used + 1)，因为我们用掉了一张优惠券。
                long long cost_with_coupon = dist[u][coupons_used]; // 桥费用为 0
                // 如果这条路径比当前已知的到达状态 (v, coupons_used + 1) 的最短路径更便宜：
                if (cost_with_coupon < dist[v][coupons_used + 1]) {
                    // 更新到达状态 (v, coupons_used + 1) 的最小费用。
                    dist[v][coupons_used + 1] = cost_with_coupon;
                    // 将这个改进后的状态（或新发现的状态）添加到优先队列中。
                    pq.push({dist[v][coupons_used + 1], v, coupons_used + 1});
                }
            }
        }
    }

    // Dijkstra 算法完成后，dist[n][i] 存储了到达目标城镇 n
    // 且恰好使用了 i 张优惠券的最小费用（如果可达）。
    // 我们需要找到所有可能的优惠券使用数量（从 0 到 k）中，到达城镇 n 的最小总费用。
    long long min_total_cost = INF; // 初始化最小总费用为无穷大。
    for (int i = 0; i <= k; ++i) {
        // 比较并更新最小总费用。
        min_total_cost = min(min_total_cost, dist[n][i]);
    }

    // 输出结果：
    // 如果 min_total_cost 仍然是 INF，说明无法从城镇 1 到达城镇 n。
    if (min_total_cost == INF) {
        cout << -1 << endl; // 输出 -1 表示不可达。
    } else {
        // 否则，输出计算得到的最小总费用。
        cout << min_total_cost << endl;
    }

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