P1073 [NOIP2009 提高组] 最优贸易

我们考虑一个中间点，求出从 \(1\) 出发到它的最小买入价，从它到 \(n\) 的最大卖出价。（从它到 \(n\) 的求解是在反向图中从 \(n\) 开始跑）

可以发现，这个做法是不会遗漏情况的。

这个问题很像最短路问题，但是注意它第一次得到的答案并不是最终答案，所以无法使用 dijkstra 求解。

我们可以用 spfa 求解它。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l,i##end=r;i<i##end;++i)
#define Rs(i,l,r) for(int i=l,i##end=r;i>i##end;--i)
#define Le(i,l,r) for(int i=l,i##end=r;i<=i##end;++i)
#define Re(i,l,r) for(int i=l,i##end=r;i>=i##end;--i)
#define L(i,l) for(int i=0,i##end=l;i<i##end;++i)
#define E(i,l) for(int i=1,i##end=l;i<=i##end;++i)
#define W(t) while(t--)
#define Wh while

const int N=100010,M=2000010;
int n,m,h[N],e[M],ne[M],idx,w[N],dis[N],dis2[N],q[N];//don't forget memset h!
bool st[N];
int min(int a,int b,bool t,int &c){//优美的代码
    int tmp=t?min(a,b):max(a,b);//判断是从哪里出发，决定求的是最大/最小
    if(tmp>c^t&&tmp!=c){//异或用来将大于小于号取反（本质上>反过来是<=，注意如果相等不判，导致死循环）
        c=tmp;
        return 1;
    }
    return 0;
}
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void spfa(int s,int dis[]){
    // cout<<s<<'\n';
    bool t=s==1;
    if(t)memset(dis+1,0x3f,n*4),memset(st+1,0,n);
    dis[s]=w[s];
    int hh=0,tt=0;
    q[tt++]=s,st[s]=1;
    Wh(hh!=tt){
        int x=q[hh++];
        st[x]=0;
        hh=hh==N?0:hh;
        Ed{
            int j=e[i];
            if(i&1^!t)continue;//判是走正向边还是反向边，利用存边的奇偶性
            if(min(w[j],dis[x],t,dis[j])&&!st[j])st[j]=1,q[tt++]=j,tt=tt==N?0:tt;
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    memset(h,-1,n*4+4);
    E(i, n)cin>>w[i];
    E(i, m){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b),add(b,a);//43行de
        if(c==2)add(b,a),add(a,b);
    }
    spfa(n,dis2);
    spfa(1,dis);
    int ans=0;
    E(i, n)ans=max(ans,dis2[i]-dis[i]);//,cout<<dis[i]<<' '<<dis2[i]<<'\n';
    cout<<ans;
    return 0;
}