题解 P1073 【最优贸易】

· · 题解

/*然而并不需要写两遍spfa

我刚开始的思路是，维护ms[i]和mb[i]两个数组，分别表示从原点到i路径中最大卖出价和最小买入价（就是最大值和最小值），然后跑spfa，用dis[e.from]更新节点e.to时顺便更新ms[]和mb[]，然而只A了一组数据

然后我仔细想了一下，ms这个数组在一次spfa中是无法更新的，因为水晶球的最大卖出价一定要倒着跑一边spfa更新，然而我懒得写了。。。

于是我想，能不能不更新ms数组，直接把将每个点的卖出价格当作ms来用呢？事实证明是可行的。可以在spfa时拿dis[e.from]和ms[e.to]-mb[e.from]更新节点e.to，类似DP的感觉，

即dis[e.from]=max(dis[e.to],ms[e.to]-mb[e.from]);

然后莫名其妙就A了。。

*/

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define maxn 100000+5
using namespace std;
struct Edges{
    int from,to;
};
vector<int>G[maxn];
vector<Edges>edge;
int n,m,dis[maxn],mb[maxn],ms[maxn];
bool vis[maxn];
inline void addedge(int u,int v){
    Edges e;
    e.from=u;e.to=v;
    edge.push_back(e);
    int m=edge.size();
    G[u].push_back(m-1);
}
int spfa(int U,int V){
    for(int i=1;i<=n;i++)dis[i]=-maxn;
    dis[U]=0;
    vis[U]=1;
    queue<int>q;
    q.push(U);
    Edges e;int u;
    while(!q.empty()){
        u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<G[u].size();i++){
            e=edge[G[u][i]];bool mark=0;
            if(dis[e.to]<ms[e.to]-mb[e.from]){
                dis[e.to]=ms[e.to]-mb[e.from];
                mb[e.to]=min(mb[e.to],mb[e.from]);
                mark=1;
            }
            if(dis[e.to]<dis[e.from]){
                dis[e.to]=dis[e.from];
                mb[e.to]=min(mb[e.to],mb[e.from]);
                mark=1;
            }
            if(mark){
                if(!vis[e.to])
                    q.push(e.to);
            }
        }
    }
    if(dis[V]>0)
        return dis[V];
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    int x,y,z;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>mb[i];
        ms[i]=mb[i];
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        addedge(x,y);
        if(z==2) addedge(y,x);
    }
    cout<<spfa(1,n);
}