自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:54:46，当前版本为作者最后更新于2024-02-02 15:14:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易发现，如果经过了 $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$。

$v_b$ 和 $v_a$ 是定值，所以只需要最小化交易次数 $k$。

对于一个交换 $x_i$ 和 $y_i$ 商品的商人，连边 $y_i \to x_i$，表示从 $y_i$ 得到 $x_i$ 需要一次交易。那么从 $a$ 到 $b$ 的最短路就是最小交换次数。

边权全为 $1$，跑 bfs 即可。

#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;
  }
}