图论、最短路、广度优先搜索、SPFA

Solution 1：首先由于我要去打 ACM 了，可以尝试用 SPFA 跑最短路。如果题目不能卡 SPFA 就直接过了，没过也不亏。

商品是点，商人的交易是边，建图然后用 SPFA 跑最短路，根据建图方法不同可能要跑最长路。

时间复杂度不会分析，由于已经有人证明了本题中 SPFA 等价于 bfs 所以是 $O(n+m)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=1'000'000'000'000'000'000ll;
struct Star{int w,to;Star(int x,int y):w(x),to(y){}};
vector<Star> v[100'005];
int n,m,S,T,w[100'005];
long long dis[100'005];
bool on[100'005];
queue<int> q;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>S>>T,++S,++T;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y,++x,++y;
        v[x].push_back(Star(w[x]-w[y]-1,y));
    }
    fill(dis+1,dis+n+1,-inf);
    on[S]=1,dis[S]=0ll;
    for(q.push(S);!q.empty();q.pop()){
        int now=q.front();
        on[now]=0;
        for(auto i:v[now]) if(dis[i.to]<dis[now]+i.w){
            dis[i.to]=dis[now]+i.w;
            if(!on[i.to]) on[i.to]=1,q.push(i.to);
        }
    }
    if(dis[T]==-inf) cout<<"No solution"<<'\n';
    else cout<<-dis[T]<<'\n';
    return 0;
}

Solution 2：分析题目本质：令一个从 $S$ 通过 $n$ 次交换得到 $T$ 的方案到达的节点依次为 $a_1 \sim a_n$，最终花费就为 $(w_{a_2}-w_{a_1}+1)+(w_{a_3}-w_{a_2}+1)+\cdots+(w_{a_n}-w_{a_{n-1}}+1) = w_{a_n}-w_{a_1}+n$。

由于题目要求从 $S$ 得到 $T$，所以 $w_{a_n}$ 和 $w_{a_1}$ 都是定值，最小化 $n$ 即可。

广度优先搜索求最小的 $n$，时间复杂度 $O(n+m)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,S,T,w[100'005],dis[100'005];
vector<int> v[100'005];
queue<int> q;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>S>>T,++S,++T;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y,++x,++y;
        v[x].push_back(y);
    }
    for(q.push(S);!q.empty();q.pop()){
        int now=q.front();
        for(int i:v[now]) if(!dis[i]) dis[i]=dis[now]+1,q.push(i);
    }
    if(dis[T]==0) cout<<"No solution"<<'\n';
    else cout<<w[T]-w[S]+dis[T]<<'\n';
    return 0;
}