T3-16 冻结

思路解析

本题是分层图最短路的又一变体。与前两题（免费边权变 0）不同，这里使用 SpellCard 是将边权减半而非归零。

唯一的区别

	Revamping Trails / 飞行路线	冻结
跨层边权	0（免费通行）	w/2（时间减半）
其余建图	完全相同	完全相同

数据规模

N ≤ 50，M ≤ 1000，K ≤ 50，非常小。分层图总共才 50×51 = 2550 个节点，甚至 O(n²) Dijkstra 或 SPFA 都能轻松通过。

---

逐行注释代码

#include <iostream>                        // 引入输入输出流
#include <vector>                          // 引入动态数组
#include <queue>                           // 引入优先队列
using namespace std;

typedef long long ll;                      // 长整型
typedef pair<ll, int> pli;                 // (距离, 节点编号)

const ll INF = 1e18;                       // 无穷大
const int MAXN = 55 * 55;                  // 最大节点数 = N * (K+1)，最多 50*51

int n, m, k;                               // 城市数、道路数、SpellCard 数
vector<pair<int, int>> adj[MAXN];          // 邻接表
ll dist_arr[MAXN];                         // 最短距离数组

// 将 (层号, 原始节点) 映射为唯一编号
// 节点从 1 开始，层从 0 开始
inline int id(int layer, int v) {
    return layer * n + v;
}

void dijkstra() {
    int total = n * (k + 1) + 1;           // 分层图总节点数（多留一点余量）
    for (int i = 0; i < total; i++)
        dist_arr[i] = INF;

    priority_queue<pli, vector<pli>, greater<pli>> pq;  // 小根堆

    dist_arr[id(0, 1)] = 0;               // 第 0 层节点 1，距离为 0
    pq.push({0, id(0, 1)});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist_arr[u]) continue;    // 过时状态跳过

        for (auto [v, w] : adj[u]) {
            if (d + w < dist_arr[v]) {
                dist_arr[v] = d + w;
                pq.push({dist_arr[v], v});
            }
        }
    }
}

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

    cin >> n >> m >> k;                    // 读入城市数、道路数、卡片数

    for (int i = 0; i < m; i++) {          // 读入 m 条道路
        int a, b, w;
        cin >> a >> b >> w;

        for (int j = 0; j <= k; j++) {     // 在每一层添加原始边（层内边）
            // 第 j 层内的双向边，权为 w（不使用卡片，正常通行）
            adj[id(j, a)].push_back({id(j, b), w});
            adj[id(j, b)].push_back({id(j, a), w});

            if (j < k) {                   // 还有卡片可用
                // ★ 关键区别：跨层边权为 w/2（使用一张卡片，时间减半）
                adj[id(j, a)].push_back({id(j + 1, b), w / 2});
                adj[id(j, b)].push_back({id(j + 1, a), w / 2});
            }
        }
    }

    dijkstra();                            // 运行 Dijkstra

    // 取所有层中到达终点 N 的最短距离的最小值
    ll ans = INF;
    for (int j = 0; j <= k; j++)           // 枚举使用了 0~k 张卡片
        ans = min(ans, dist_arr[id(j, n)]);

    cout << ans << endl;                   // 输出最少用时

    return 0;
}