首发题解，庆祝一下

大家好，我是энтджей，今天是我2026年第十八次正式发题解！

2026年发布的题解！

能不能点个赞

---

首先简化题意：

• 共有 $N$ 种商品，第 $i$ 种商品的价格为 $v_i$，现在有 $M$ 种交换方式，第 $i$ 种交换方式为 将序号为 $x$ 的商品换为序号为 $y$ 的商品，并且你会获得（或失去）$v_x - v_y - 1$ 元钱。你现在手上有商品 $a$ ，你希望通过交易，用最少得钱，将 $a$ 交换为 $b$ 。

然后就是写代码:

• 处理输入（read）：

  • 正常输入

• 核心部分（process）：

  • 可以直接广搜，然后输出
  • 但是如果直接广搜，广搜 手上是什么序号的上商品，花了多少钱，这样会超时（好像，反正不能A）
  • 那么只能优化：
    • 注意到将 $a$ 换成 $b$，假设换了 $n$ 次后，手上的商品为 $b$，其中，换了 $i$ ，次后手上的商品为 $s_i$，则总花费为：
      $(v_{s_1} - v_a - 1) + (v_{s_2} - v_{s_1} - 1) + \cdots + (v_b - v_{s_{n-1}} - 1)$
      $= v_{s_1} - v_a - 1 + v_{s_2} - v_{s_1} - 1 + \cdots + v_b - v_{s_{n-1}} - 1$
      $= -v_a + v_b + \underbrace{(-1 - 1 - \cdots - 1)}_{n\text{个}}$
      $= v_b - v_a - n$
    • 所以实际的花费只和 $a$、$b$ 和 交换次数 有关

最后输出（write）：

• 输出结果

完整代码：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int N = 1e5 + 10;
int n, m, a, b;
int v[N];
vector<int> ve[N];
bool vis[N];
void read() {
    cin >> n >> m >> a >> b;
    for(int i = 0; i <  n; i++) {
        cin >> v[i];
    }
    for(int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);
    }
}
void ProcessWrite() {
    queue<int> q;
    q.push(a);
    vis[a] = true;
    int cnt = 0;  // cnt = 当前BFS层数 = 已进行的交换次数
    while(!q.empty()) {
        for(int i = q.size(); i >= 1; i--) {
            int u = q.front();
            q.pop();
            if(u == b) {
                cout << v[b] - v[a] + cnt;
                return ;
            }
            for( auto t : ve[u] ) {
                if(!vis[t]) {
                    q.push(t);
                    vis[t] = true;
                }
            }
        }
        cnt++;
    }
    cout << "No solution";
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    read();
    ProcessWrite();
    return 0;
}

---

🎉完结撒花🎉