T3-14 Revamping Trai

思路解析

问题本质

从节点 1 到节点 N 的最短路，但可以将最多 K 条边的权值变为 0。

核心思路：分层图

构建 K+1 层图（第 0 层到第 K 层），每一层代表"已经使用了多少次免费改造"：

• 层内边：对于原图每条边 (u, v, w)，在每一层都保留原边 u → v（权 w）
• 跨层边：对于原图每条边 (u, v, w)，添加从第 j 层到第 j+1 层的边 u → v（权 0），表示"改造这条边"

从第 0 层的节点 1 出发跑 Dijkstra，答案是 $min_{j=0}^{K}\text{dist}[\text{第 j 层的节点 N}]$。

图解

第0层:  1 --w-- 2 --w-- ... --w-- N    （没用过免费机会）
         \       \                 
          0       0               ← 跨层边（权0，消耗一次机会）
           \       \              
第1层:  1 --w-- 2 --w-- ... --w-- N    （已用1次免费）
           \       \              
            0       0             
             \       \            
第2层:  1 --w-- 2 --w-- ... --w-- N    （已用2次免费）
...
第K层:  1 --w-- 2 --w-- ... --w-- N    （已用K次免费）

复杂度

• 节点数：$N \times (K+1)$
• 边数：$M \times (K+1) \times 2$（层内）+ $M \times K \times 2$（跨层）
• 时间：$O(K \cdot (N + M) log(NK))$
• 空间：$O(NK + MK)$

---

逐行注释代码

#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 = 10005 * 21;               // 最大节点数 = N * (K+1)

int n, m, k;                               // n: 牧场数, m: 小径数, k: 可改造次数
vector<pair<int, int>> adj[MAXN];          // 邻接表，adj[u] 存 {v, w}
ll dist_arr[MAXN];                         // 最短距离数组

// 将 (层号 layer, 原始节点 v) 映射为分层图中的节点编号
// 编号方式：layer * n + v（节点从1开始，层从0开始）
inline int id(int layer, int v) {
    return layer * n + v;                  // 唯一编号
}

void dijkstra() {
    int total = n * (k + 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);           // 加速 IO
    cin.tie(nullptr);

    cin >> n >> m >> k;                    // 读入牧场数、小径数、可改造次数

    for (int i = 0; i < m; i++) {          // 读入 m 条小径
        int u, v, w;
        cin >> u >> v >> w;

        for (int j = 0; j <= k; j++) {     // 在每一层都添加原始边（层内边）
            // 层 j 内的双向边，权为 w
            adj[id(j, u)].push_back({id(j, v), w});
            adj[id(j, v)].push_back({id(j, u), w});

            if (j < k) {                   // 如果还有改造次数可用
                // 跨层边：从第 j 层到第 j+1 层，权为 0（代表改造这条边）
                adj[id(j, u)].push_back({id(j + 1, v), 0});
                adj[id(j, v)].push_back({id(j + 1, u), 0});
            }
        }
    }

    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;
}