P10110 [GESP202312 七级] 商品交易
一扶苏一
·
·
题解
容易发现，如果经过了 k 次交易后从 a 得到 b，假设商品的交易过程是 a \to x_1 \to x_2 \to \dots \to x_{k - 1} \to b，那么收益就是 (v_{x_1} - v_a + 1) + (v_{x_2} + v_{x_1} + 1) + \dots + (v_b - v_{k - 1} + 1)。把 +1 都提出来，共有 k 个。余下的项去括号，可以看到 v_{x_i} 的符号以正负各出现了一次，被抵消掉了。所以总收益就是 v_b - v_a + k。
对于一个交换 $x_i$ 和 $y_i$ 商品的商人，连边 $y_i \to x_i$，表示从 $y_i$ 得到 $x_i$ 需要一次交易。那么从 $a$ 到 $b$ 的最短路就是最小交换次数。
边权全为 $1$，跑 bfs 即可。
```cpp
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, a, b;
std::cin >> n >> m >> a >> b;
std::vector<int> v(n);
for (auto &i : v) std::cin >> i;
std::vector<std::vector<int>> chg(n);
for (int x, y; m; --m) {
std::cin >> x >> y;
chg[x].push_back(y);
}
std::vector<int> f(n, 1100000000);
f[a] = 0;
std::queue<int> Q;
for (Q.push(a); !Q.empty(); Q.pop()) {
int u = Q.front();
for (auto v : chg[u]) {
if (f[v] > f[u] + 1) {
f[v] = f[u] + 1;
Q.push(v);
}
}
}
if (f[b] == 1100000000) {
std::cout << "No solution\n";
} else {
std::cout << f[b] + v[b] - v[a] << std::endl;
}
}
```