[BJWC2012] 冻结

GitHub 跳转原题关系图返回列表

把状态定义成"当前所在城市 + 已用卡数"。走一条边时要么正常通过，要么额外消耗一张卡把这条边代价减半，在这个状态图上跑 Dijkstra。

OJ: luogu

题目 ID: P4822

难度:普及+/提高

标签:最短路图论堆

日期: 2026-06-20 04:58

题意

给你一张无向带权图，从 $1$ 走到 $N$ 。

你有最多 $K$ 张卡。
每张卡只能在一条边上使用一次，效果是把这条边的通过时间减半。

要求输出从 $1$ 到 $N$ 的最小时间。
不要求把卡全部用完。

思路

先看一个更直观的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
const long long INF = (1LL << 60);

int n, m, k;
long long dist_arr[105][105];

int state_id(int city, int used) {
    return used * n + city;
}

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

    cin >> n >> m >> k;

    int tot = (k + 1) * n;
    for (int i = 1; i <= tot; i++) {
        for (int j = 1; j <= tot; j++) {
            if (i == j) {
                dist_arr[i][j] = 0;
            }
            else {
                dist_arr[i][j] = INF;
            }
        }
    }

    // 直接把分层图完整建出来：
    // 第 used 层表示已经用了 used 张卡。
    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;

        for (int used = 0; used <= k; used++) {
            int a = state_id(u, used);
            int b = state_id(v, used);
            if (len < dist_arr[a][b]) {
                dist_arr[a][b] = len;
                dist_arr[b][a] = len;
            }

            if (used < k) {
                int c = state_id(u, used);
                int d = state_id(v, used + 1);
                if (len / 2 < dist_arr[c][d]) {
                    dist_arr[c][d] = len / 2;
                }

                c = state_id(v, used);
                d = state_id(u, used + 1);
                if (len / 2 < dist_arr[c][d]) {
                    dist_arr[c][d] = len / 2;
                }
            }
        }
    }

    for (int mid = 1; mid <= tot; mid++) {
        for (int i = 1; i <= tot; i++) {
            if (dist_arr[i][mid] >= INF / 2) {
                continue;
            }
            for (int j = 1; j <= tot; j++) {
                if (dist_arr[mid][j] >= INF / 2) {
                    continue;
                }
                long long nd = dist_arr[i][mid] + dist_arr[mid][j];
                if (nd < dist_arr[i][j]) {
                    dist_arr[i][j] = nd;
                }
            }
        }
    }

    long long answer = INF;
    for (int used = 0; used <= k; used++) {
        if (dist_arr[state_id(1, 0)][state_id(n, used)] < answer) {
            answer = dist_arr[state_id(1, 0)][state_id(n, used)];
        }
    }

    cout << answer << '\n';

    return 0;
}

brute.cpp 直接把"用了几张卡"这件事展开成分层图：

第 $0$ 层：一张卡都还没用
第 $1$ 层：已经用过 $1$ 张
…
第 $K$ 层：已经用过 $K$ 张

如果原图里有一条边 $u \leftrightarrow v$ ，那么在分层图里就有两种走法：

不用卡：
- 还留在当前层
- 花费原边权
用卡：
- 跳到下一层
- 花费原边权的一半

这个思路完全贴着题意，但直接把整张分层图展开出来再跑 Floyd，只适合很小的数据。

真正的主解不必显式建出整张分层图，只需要把状态写进 Dijkstra 里。

状态定义

设：

$dist[u][used]$ 表示到达城市 $u$ ，并且已经用了 $used$ 张卡时的最短时间

那么从 $(u, used)$ 走一条边到 $v$ 时，有两种转移：

不用卡：
- 到 $(v, used)$
- 代价加 $w$
如果 $used < K$ ，还可以用卡：
- 到 $(v, used + 1)$
- 代价加 $w / 2$

这个过程可以用下面这张图来理解：

flowchart LR
  A["(u, used)"] -->|"w"| B["(v, used)"]
  A -->|"w/2"| C["(v, used+1)"]

图里每一次"向下一层"就代表多消耗了一张卡。
而"留在本层"则表示这条边正常通过。

因为所有边权都非负，所以在这个状态图上直接跑 Dijkstra 就可以了。

最后答案不是只看 $dist[N][K]$ ，而是：

$dist[N][0 \dots K]$ 的最小值

因为卡片可以不用完。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50 + 5;
const int MAXM = 1000 * 2 + 5;
const long long INF = (1LL << 60);

struct HeapNode {
    int u;
    int used;
    long long dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n, m, k;
int head[MAXN], to[MAXM], nxt[MAXM], w[MAXM], edge_cnt;
long long dist_arr[MAXN][MAXN];
bool vis[MAXN][MAXN];

void init_graph() {
    edge_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = 0;
    }
}

void add_edge(int u, int v, int len) {
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = len;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

void dijkstra() {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dist_arr[i][j] = INF;
            vis[i][j] = false;
        }
    }

    priority_queue<HeapNode> pq;
    dist_arr[1][0] = 0;
    pq.push({1, 0, 0});

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        int used = cur.used;
        if (vis[u][used]) {
            continue;
        }
        vis[u][used] = true;

        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            long long nd = dist_arr[u][used] + w[i];
            if (nd < dist_arr[v][used]) {
                dist_arr[v][used] = nd;
                pq.push({v, used, nd});
            }

            // 在这条边上再额外用一张卡，时间减半。
            if (used < k) {
                long long freeze_dist = dist_arr[u][used] + w[i] / 2;
                if (freeze_dist < dist_arr[v][used + 1]) {
                    dist_arr[v][used + 1] = freeze_dist;
                    pq.push({v, used + 1, freeze_dist});
                }
            }
        }
    }
}

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

    cin >> n >> m >> k;
    init_graph();

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        add_edge(u, v, len);
        add_edge(v, u, len);
    }

    dijkstra();

    long long answer = INF;
    for (int used = 0; used <= k; used++) {
        if (dist_arr[n][used] < answer) {
            answer = dist_arr[n][used];
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

状态数是：

$N \times (K + 1)$

每条原图边在每一层里都会产生常数条转移。
因此总复杂度大致是：

$O(KM \log (NK))$

在本题 $N \leqslant 50, M \leqslant 1000, K \leqslant 50$ 的范围内完全足够。

空间复杂度：

$O(NK)$

总结

这题最重要的不是"边权减半"本身，而是把它翻译成状态。

一旦你把"已经用了多少张卡"加进状态里，问题就重新变回了最熟悉的那种：

非负权状态图最短路

所以它本质上是一道非常标准的分层图 / 状态最短路题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P4822 [BJWC2012] 冻结

题目背景

“我要成为魔法少女！”

“那么，以灵魂为代价，你希望得到什么？”

“我要将有关魔法和奇迹的一切，封印于卡片之中„„”

在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。

现在，不需要立下契约也可以使用魔法了！你还不来试一试？

比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。

例如，我们熟知的 Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。

这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、……

当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。

题目描述

我们考虑最简单的旅行问题吧：现在这个大陆上有 $N$ 个城市， $M$ 条双向的道路。城市编号为 $1$ ~ $N$ ，我们在 $1$ 号城市，需要到 $N$ 号城市，怎样才能最快地到达呢？

这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall 等算法来解决。

现在，我们一共有 $K$ 张可以使时间变慢 $50\%$ 的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是：

在一条道路上最多只能使用一张 SpellCard。
使用一张 SpellCard 只在一条道路上起作用。
你不必使用完所有的 SpellCard。

给定以上的信息，你的任务是：求出在可以使用这不超过 $K$ 张时间减速的 SpellCard 之情形下，从城市 $1$ 到城市 $N$ 最少需要多长时间。

输入格式

第一行包含三个整数： $N$ 、 $M$ 、 $K$ 。

接下来 $M$ 行，每行包含三个整数： $A_i$ 、 $B_i$ 、 $Time_i$ ，表示存在一条 $A_i$ 与 $B_i$ 之间的双向道路，在不使用 SpellCard 之前提下，通过它需要 $Time_i$ 的时间。

输出格式

输出一个整数，表示从 $1$ 号城市到 $N$ 号城市的最小用时。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

样例 1 解释

在不使用 SpellCard 时，最短路为 $1 \to 2 \to 4$ ，总时间为 $10$ 。现在我们可以使用 $1$ 次 SpellCard，那么我们将通过 $2 \to 4$ 这条道路的时间减半，此时总时间为 $7$ 。

数据规模与约定

对于 $100\%$ 的数据，保证：

$1 \leq K \leq N \leq 50$ ， $M \leq 10^3$ 。
$1 \leq A_i,B_i \leq N$ ， $2 \leq Time_i \leq 2 \times 10^3$ 。
为保证答案为整数，保证所有的 $Time_i$ 均为偶数。
所有数据中的无向图保证无自环、重边，且是连通的。

[BJWC2012] 冻结

目录

题意

思路

状态定义

代码

复杂度

总结

一图流解析