这道题是分层图最短路的经典入门题，核心是把「最多K次边权减半」的限制转化为分层图的维度，最终用最短路算法求解从1号点到N号点的最小通行时间。

📌 题目核心模型

给定N个点、M条双向带权边，从1号点出发到N号点

最多可使用K次「冻结」技能，每次让单条边的通行时间减半（向下取整）

不需要用完所有K次技能，求全局最短总时间

数据范围：

1

≤

𝐾

≤

𝑁

≤

50

1≤K≤N≤50，

𝑀

≤

1000

M≤1000，所有边权均为偶数保证结果为整数

❌ 错误思路避坑

暴力枚举不可行‌：直接枚举哪K条边减半，组合数随K指数级增长，K=20时运算量达到

1

0

50

10

50

量级，完全无法通过

贪心思路错误‌：先跑原图最短路，再在路径上选最长的K条边减半，无法保证全局最优——最优路径可能根本不在原图的最短路径上，局部最优不能替代全局最优

🧩 分层图建模思路

分层图的核心是把「已使用的冻结次数」作为独立维度，将原图复制成‌K+1层‌：

第0层：完全不使用任何冻结技能，所有边权保持原图的w

第i层（1≤i≤K）：表示已经使用了i次冻结技能，层内边权仍为原图的w

跨层连边：从第i层的u点向第i+1层的v点连一条边权为w/2的边，代表在这条边上消耗1次冻结技能，边权减半

最终答案：取第0层到第K层中，所有N号点的最短距离的最小值，允许技能不用完

💻 两种主流实现方式

1. 显式分层图实现（物理建图）

直接构建完整的分层图，将第i层的u点映射为节点编号 i * n + u，在新图上跑堆优化Dijkstra即可。

cpp

#include <bits/stdc++.h>

using namespace std;

const int maxn = 55, maxk = 55;

const int inf = 0x3f3f3f3f;

typedef pair<int, int> pii;

int head[maxn * maxk], cnt = 0;

struct Edge {

    int v, next, w;

} e[1000 * maxk * 4];

void add(int u, int v, int w) {

    e[cnt].v = v; e[cnt].w = w;

    e[cnt].next = head[u]; head[u] = cnt++;

}

int n, m, k;

int dis[maxn * maxk];

bool vis[maxn * maxk];

void dijkstra(int s) {

    memset(vis, 0, sizeof(vis));

    memset(dis, inf, sizeof(dis));

    dis[s] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> q;

    q.push({0, s});

    while (!q.empty()) {

        int u = q.top().second; q.pop();

        if (vis[u]) continue;

        vis[u] = 1;

        for (int i = head[u]; i != -1; i = e[i].next) {

            int v = e[i].v;

            if (dis[v] > dis[u] + e[i].w) {

                dis[v] = dis[u] + e[i].w;

                q.push({dis[v], v});

            }

        }

    }

}

int main() {

    memset(head, -1, sizeof(head));

    cin >> n >> m >> k;

    for (int i = 1; i <= m; i++) {

        int u, v, w;

        cin >> u >> v >> w;

        // 第0层正常连边

        add(u, v, w); add(v, u, w);

        // 构建1~k层的层内边和跨层边

        for (int j = 1; j <= k; j++) {

            add(u + (j-1)*n, v + j*n, w/2);

            add(v + (j-1)*n, u + j*n, w/2);

            add(u + j*n, v + j*n, w);

            add(v + j*n, u + j*n, w);

        }

    }

    dijkstra(1);

    int ans = inf;

    for (int i = 0; i <= k; i++)

        ans = min(ans, dis[n + i * n]);

    cout << ans << endl;

    return 0;

}

该实现节点总数最多为

50

×

51

=

2550

50×51=2550，边数规模极小，Dijkstra可以瞬间跑完

2. 状态压缩实现（DP式最短路）

不显式构建分层图，直接用二维数组dist[used][u]记录「使用了used次技能，到达u点的最短时间」，在普通最短路的松弛过程中同时处理两种转移：

不使用技能：dist[used][v] = min(dist[used][v], dist[used][u] + w)

使用技能：dist[used+1][v] = min(dist[used+1][v], dist[used][u] + w/2)

这种写法更省内存，也不容易出现节点编号映射错误的问题，竞赛中更推荐使用

🔍 样例验证

输入样例：

text

4 4 1

1 2 4

4 2 6

1 3 8

3 4 8

原图不使用技能的最短路是1→2→4，总时间10

使用1次技能将2→4的边权减半为3，总时间变为4+3=7，与样例输出完全一致

需要我为你整理‌分层图最短路的同类经典题单‌吗？帮你快速巩固这类建模技巧。