P4568 [JLOI2011] 飞行路线

#include <bits/stdc++.h>

using namespace std;

// 定义无穷大常量，用于初始化距离数组
constexpr int inf = 0x3f3f3f3f;

// 定义边的结构体，用于邻接表和优先队列
struct Edge {
    int u, w; // u: 边的目标节点 (target node), w: 边的权值 (cost)

    // 重载小于号运算符 <
    // std::priority_queue 默认是大根堆（最大的元素在堆顶）
    // 为了让它变成小根堆（最小权值的边在堆顶），我们需要反转比较逻辑
    // 当当前边的权值 w 大于对方的权值 o.w 时，判定为“真”，使其沉底
    bool operator< (const Edge& o) const {
        return w > o.w;
    }
};

int main() {
    // 关闭输入输出同步，加速 I/O 操作
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k, s, t;
    // 输入：城市数 n，航线数 m，免费次数 k，起点 s，终点 t
    cin >> n >> m >> k >> s >> t;

    // 坐标偏移处理：题目给出的城市编号是 0 ~ n-1
    // 这里将其统一加 1，变为 1 ~ n，符合部分人的编程习惯（不加也可以，只要统一就行）
    s++; t++;

    // 初始化邻接表
    // 分层图共有 k+1 层（第0层到第k层）
    // 总节点数约为 n * (k + 1)，为了防止越界，开大一点点
    vector<vector<Edge> > adj((k + 1) * n + 1);

    // 读取 m 条航线信息
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u++; v++; // 同样将输入的节点编号加 1

        // 1. 建立第 0 层的原始边（完全不使用免费票的情况）
        // 连接 u 和 v，权值为 w
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});

        // 2. 遍历第 1 层到第 k 层，构建分层图的其余部分
        for (int j = 1; j <= k; ++j) {
            // --- 策略 A：同层移动（不使用免费票） ---
            // 在第 j 层，连接 u 和 v，花费仍然是 w
            // 节点编号映射规则：第 j 层的节点 u 编号为 j * n + u
            adj[j * n + u].push_back({j * n + v, w});
            adj[j * n + v].push_back({j * n + u, w});

            // --- 策略 B：跨层移动（使用免费票） ---
            // 从第 j-1 层跨越到第 j 层，花费为 0
            // 这代表：在当前这条航线上使用了 1 次免费机会

            // 从 u (第 j-1 层) -> v (第 j 层)，权值 0
            adj[(j - 1) * n + u].push_back({j * n + v, 0});

            // 从 v (第 j-1 层) -> u (第 j 层)，权值 0
            adj[(j - 1) * n + v].push_back({j * n + u, 0});
        }
    }

    // Dijkstra 算法标准模板
    priority_queue<Edge> q;
    // dist 数组初始化为无穷大
    vector<int> dist((k + 1) * n + 1, inf);
    // vis 数组标记节点是否已确定最短路
    vector<bool> vis((k + 1) * n + 1);

    // 起点入队：起点 s 位于第 0 层，距离为 0
    q.push({s, 0});
    dist[s] = 0;

    while (!q.empty()) {
        Edge now = q.top();
        q.pop();
        int u = now.u; // 当前节点编号（包含了层级信息）

        // 如果该节点已经处理过最优解，跳过
        if (vis[u])
            continue;
        vis[u] = true;

        // 遍历所有邻接边
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].u; // 目标节点
            int w = adj[u][i].w; // 边权

            // 松弛操作：如果通过 u 到达 v 的距离更短，则更新
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push({v, dist[v]});
            }
        }
    }

    // 统计答案
    // 最终到达终点 t 时，可能使用了 0 次、1 次 ... 或 k 次免费票
    // 这些状态分别对应分层图中的 t, n+t, 2n+t ... k*n+t
    // 取所有可能层级中终点距离的最小值
    int ans = inf;
    for (int i = 0; i <= k; ++i) {
        ans = min(ans, dist[i * n + t]);
    }

    cout << ans << "\n";

    return 0;
}