交换 x → y 的花费是 v_y − v_x + 1;求从商品 a 换到 b 的最小花费(可以为负)。
市场上有 N 种商品(编号 0 … N − 1),第 i 种商品价值 vᵢ 元。共有 M 个商人,第 j 个商人处可以用第 xⱼ 种商品换第 yⱼ 种商品。
交易按商品价值结算:若 v_{xⱼ} > v_{yⱼ},商人付给你 v_{xⱼ} − v_{yⱼ} 元;否则你要付给商人 v_{yⱼ} − v_{xⱼ} 元。此外每次交易商人都要收 1 元手续费,不论价值孰高孰低。
你现在持有商品 a,希望通过若干次交换得到商品 b。求至少需要花多少钱(最小花费可能是负数,表示你在完成目标的同时还赚了钱)。如果无法换到商品 b,输出 No solution。
输入:第一行 N、M、a、b;第二行 v₀ … v_{N−1};随后 M 行,每行 xⱼ yⱼ。
v_y − v_x + 1。d[i] 表示"换到商品 i 的最小花费",再令 g[i] = d[i] − v_i,于是每次交换恰好让 g 增加 1:g[y] = g[x] + 1。g[a] = d[a] − v_a = −v_a,所以 g[b] = −v_a + ℓ,其中 ℓ 是路径上的交换次数;于是 d[b] = v_b − v_a + ℓ。有向图最短路负权边换元(势能函数)无权图 BFS
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N、M、a、b;第二行 v₀ … v_{N−1};之后 M 行每行 xⱼ yⱼ |
| 输出 | 最小花费;无法换到 b 则输出 No solution |
| 数据范围 | N ≤ 10⁵,M ≤ 2 × 10⁵,1 ≤ vᵢ ≤ 10⁹ |
| 交易花费 | 用 x 换 y:先按差价结算(可为负),再交 1 元手续费 |
| 边的方向 | 有向边 x → y(用 x 换 y,不能反向) |
| 约束 | a ≠ b,xⱼ ≠ yⱼ |
v_y − v_x + 1 在 v_y < v_x 时是负数,Dijkstra 建立在"边权非负"之上,遇到负权会得出错误答案a = u₀ → u₁ → … → u_ℓ = b 的总花费为 Σ (v_{u_{i+1}} − v_{u_i} + 1) = v_b − v_a + ℓ,中途所有商品的价值两两抵消(望远镜求和),只剩首尾两个价值和一个"交换次数";而 v_b − v_a 是常数,所以只需要最少交换次数dist[b] 就是 ℓ;若 b 不可达则无解数据:v = [1, 2, 4];边为 1→0、2→0、0→1、2→1、1→2。
dist[0] = 0(起点)
从 0 出发:0 → 1,dist[1] = 1
从 1 出发:1 → 2,dist[2] = 2
所以 ℓ = dist[2] = 2
✅ ℓ = 2
第 1 步:用商品 0(价值 1)换商品 1(价值 2)
付差价 2 − 1 = 1 元,加手续费 1 元,共 2 元
第 2 步:用商品 1(价值 2)换商品 2(价值 4)
付差价 4 − 2 = 2 元,加手续费 1 元,共 3 元
累计 2 + 3 = 5 元
✅ 5
用公式核对:v₂ − v₀ + ℓ = 4 − 1 + 2 = 5 ✓
(2 − 1 + 1) + (4 − 2 + 1) = 2 + 3 = 5,其中中间商品的价值 2 被"减一次、加一次"抵消掉了,结果恰好是 v₂ − v₀ + 2。样例 2 数据:N = 3, M = 3, a = 0, b = 2,v = [100, 2, 4],边为 0→1、1→2、0→2。
BFS:dist[1] = 1,dist[2] = 1(有直接边 0 → 2)
所以 ℓ = 1,花费 = v₂ − v₀ + 1 = 4 − 100 + 1 = −95
另一条路 0 → 1 → 2 要走 2 步:
花费 = 4 − 100 + 2 = −94 > −95,更差
✅ −95(净赚 95 元)
数据:N = 4, M = 4, a = 3, b = 0,v = [1, 2, 3, 4]
边为 1→0、0→1、3→2、2→3
BFS:从 3 只能到 2(dist[3] = 0, dist[2] = 1),
再走回 3,仍然在 {2, 3} 这个连通块里打转
dist[0] 始终是 −1 → 换不到商品 0
✅ No solution
| 样例 | 最短交换次数 ℓ | v_b − v_a | 最小花费 | 说明 |
|---|---|---|---|---|
| 2(走 0→2) | 1 | 4 − 100 = −96 | −95 | 价值暴跌 → 倒赚 |
| 2(走 0→1→2) | 2 | −96 | −94 | 步数多一步,就多花 1 元 |
| 3 | 不可达 | 3 − 4 = −1 | No solution | 两个连通块互不相通 |
v_b − v_a + ℓ 里 v_b − v_a 本来就可正可负。v_y − v_x + 1 当边权跑 Dijkstra,就会在负权边上出错。而换元之后,"边权"变成了统一的 1,负值全部被吸收进常数项,问题彻底变干净。g[i] = d[i] − v_i 后每条边让 g 恰好加 1,于是只需求"最少交换次数"
把边权看成 v_y − v_x + 1,硬做带权最短路
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 换元 + BFS | O(N + M) = 3 × 10⁵ | ✅ 稳过 |
| SPFA | 最坏 O(NM) = 2 × 10¹⁰ | ❌ 可能被卡 |
| Dijkstra | — | ❌ 存在负权边,结论错误 |
第一行 N M a b;第二行 v 数组(N 个数);随后 M 行每行 x y(用 x 换 y)。程序做 BFS 并给出最短交换路径。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int N, M, a, b; scanf("%d %d %d %d", &N, &M, &a, &b); vector<long long> v(N); for (int i = 0; i < N; i++) scanf("%lld", &v[i]); vector<vector<int>> adj(N); for (int j = 0; j < M; j++) { int x, y; scanf("%d %d", &x, &y); adj[x].push_back(y); // 有向边:用 x 换 y } // 无权图 BFS:dist[i] = 从 a 出发到 i 的"最少交换次数" vector<int> dist(N, -1); queue<int> q; dist[a] = 0; q.push(a); while (!q.empty()) { int u = q.front(); q.pop(); for (int w : adj[u]) { if (dist[w] == -1) { // 每个点只入队一次 → O(N + M) dist[w] = dist[u] + 1; q.push(w); } } } if (dist[b] == -1) puts("No solution"); else printf("%lld\n", v[b] - v[a] + (long long)dist[b]); return 0; }
v[b] − v[a] + dist[b]?一条路径的总花费是Σ (v_y − v_x + 1),相邻项里中间商品的价值一加一减正好抵消,只剩下 v_b − v_a 再加上"交换了多少次"(每次贡献 1 元手续费)。dist[b](最少交换次数)就是这里要的 ℓ。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
adj[x].push_back(y) | 建有向边 | 用 x 换 y 是单向的,千万别建成双向 |
dist[a] = 0; q.push(a) | BFS 起点 | 你手上的商品 a 是一切交换的出发点 |
if (dist[w] == -1) { dist[w] = dist[u] + 1; } | 无权最短路核心 | 第一次访问即最优(每层代价都是 1) |
dist[b] == -1 | 无解判定 | b 从未被访问 → 换不到 → 输出 No solution |
v[b] - v[a] + dist[b] | 答案公式 | 望远镜求和的结果,恰是"最少花费" |
No solution;⑤ 用 int 存答案:v 最大 10⁹,v_b − v_a 可达 ±10⁹,再加上 M 的偏移,必须用 long long。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 0 2 | 5 | 题面样例 1(v₂ − v₀ + 2 = 5) |
3 3 0 2 | −95 | 题面样例 2(花费为负 = 倒赚) |
4 4 3 0 | No solution | 题面样例 3(两个连通块,互不相通) |
2 1 0 1 | 1 | 价值相同:只剩 1 元手续费 |
2 1 0 1 | −98 | 价值暴跌:倒赚 99 元,再交 1 元手续费 |
4 4 0 3 | 31 | 两条路(1 步 vs 3 步),选边数少的 |
v_y − v_x + 1 可能为负,Dijkstra 会给出错误结果。dist[b] == −1 时必须输出 No solution,不能输出某个数字。邻接表约 2 × 10⁵ 条边 + dist 数组 10⁵ 个 int + v 数组 10⁵ 个 long long。
✅ 约 30 万次操作,瞬间完成。换元把"带权最短路"变成了"无权最短路",这才是本题真正的考点——而不是写一个能处理负权的最短路算法。
// 一条路径的总花费 = v_b − v_a + 交换次数(中途价值全部抵消) // (v_{u1} − v_{u0} + 1) + (v_{u2} − v_{u1} + 1) + … + (v_{uℓ} − v_{uℓ−1} + 1) // = v_b − v_a + ℓ // 换元:令 g[i] = d[i] − v_i // 交换 x → y 时 d[y] = d[x] + (v_y − v_x + 1) // 代入得 g[y] = g[x] + 1 <-- 每条边都恰好让 g 加 1 // 又 g[a] = d[a] − v_a = −v_a // 所以 g[b] = −v_a + ℓ ==> d[b] = v_b − v_a + ℓ // 最小化 d[b] <=> 最小化 ℓ <=> 无权图最短路 <=> BFS dist[a] = 0; q.push(a); while (!q.empty()) { int u = q.front(); q.pop(); for (int w : adj[u]) if (dist[w] == -1) { dist[w] = dist[u] + 1; q.push(w); } } if (dist[b] == -1) puts("No solution"); else printf("%lld\n", v[b] - v[a] + dist[b]); // 通用思想:如果边权能写成 w(x → y) = φ(y) − φ(x) + c // (本题 φ = 商品价值,c = 1),那么"路径代价"只与边数有关, // 于是带权最短路退化为无权最短路,直接 BFS。
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 换元(势能函数) | 把 d[i] − v_i 当成新变量,边权化为常数 1 | 边权形如 φ(y) − φ(x) + c 的最短路、差分约束 |
| 望远镜求和 | 路径花费只看首尾价值 + 边数 | 差分、前缀和、路径长度无关中间量的计数 |
| 无权最短路 BFS | 求"最少交换次数" | 最少步数、最少操作次数、最少跳数类问题 |
v_b − v_a + Σf,需要按边权 fⱼ 求最短路;只要 fⱼ ≥ 0 就可以用 Dijkstra,但"每条边权重不同"让 BFS 不再适用。所以"手续费恰好是常数 1"才是本题能用 BFS 的关键前提。)