G7001 [GESP202312 七级] 商品交易 题解

知识点：广度优先搜索、最短路、势能转换。

解题思路

每次交易代价可写成目标商品价减当前价再加1，沿路线求和时价格差抵消，仅剩v[b]-v[a]+边数。因此在有向图上BFS求a到b最少边数。

为什么正确

首尾之外的价格项两两抵消，路线费用只随交易次数增长；等权BFS得到最少次数即最小费用。

易错点

图有方向，不能补反向边；不可达时输出No solution，注意大小写。

复杂度

时间O(n+m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    vector<long long>v(n);
    for(auto &x:v)cin>>x;
    vector<vector<int>>g(n);
    while(m--) {
        int u,w;
        cin>>u>>w;
        g[u].push_back(w);
    }
    vector<int>d(n,-1),q= {
        a
    }
    ;
    d[a]=0;
    for(int k=0;k<(int)q.size();k++)for(int v:g[q[k]])if(d[v]<0) {
        d[v]=d[q[k]]+1;
        q.push_back(v);
    }
    if(d[b]<0)cout<<"No solution";
    else cout<<v[b]-v[a]+d[b];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。