T3-15 飞行路线

思路解析

本题与上一题 Revamping Trails G 本质完全相同——分层图最短路。区别仅在于：

• 节点编号从 0 开始
• 起点终点自定义（不固定为 1 和 N）
• 可能存在重边

建图方式回顾（K+1 层分层图）

• 层内边：每层保留原图所有边（权 w）
• 跨层边：从第 j 层到第 j+1 层，权为 0（表示免费搭乘一次）

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

---

逐行注释代码

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

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

const ll INF = 1e18;                       // 无穷大
const int MAXN = 10005 * 11;               // 最大节点数 = n * (k+1)，k最大10

int n, m, k, s, t;                         // 城市数、航线数、免费次数、起点、终点
vector<pair<int, int>> adj[MAXN];          // 邻接表
ll dist_arr[MAXN];                         // 最短距离数组

// 将 (层号, 原始节点) 映射为分层图中的节点编号
// 节点从 0 开始编号，层从 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, s)] = 0;               // 第 0 层起点 s，距离为 0
    pq.push({0, id(0, s)});               // 入队

    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;                    // 读入城市数、航线数、免费次数
    cin >> s >> t;                         // 读入起点和终点

    for (int i = 0; i < m; i++) {          // 读入 m 条航线
        int a, b, c;
        cin >> a >> b >> c;

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

            if (j < k) {                   // 还有免费次数可用
                // 跨层边：从第 j 层到第 j+1 层，权为 0（使用一次免费机会）
                adj[id(j, a)].push_back({id(j + 1, b), 0});
                adj[id(j, b)].push_back({id(j + 1, a), 0});
            }
        }
    }

    dijkstra();                            // 运行 Dijkstra

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

    cout << ans << endl;                   // 输出最少花费

    return 0;
}