题目大意

有一些城市，每个城市的水晶球的售价不同。在一条从1到n的路径中，我们可以在其中一个城市买入，另一个城市卖出。

求最大收获。

算法

SPFA

先构造一个分层图，层内的边权值为0，表示随便走不需要钱。

然后第一层往第二层可以到达的点连边，权值为售价的相反数，表示买入需要花钱。

第二层往第三层可以到达的点连边，权值为售价，表示卖出可以赚钱。

然后将第一层的N和第二层的N向汇点连边，分别表示不买和买了。

然后从1开始SPFA最长路即可。

代码

#include <cstdio>
#include <queue>
#include <memory.h>
#define d1(x) (x)
#define d2(x) (x+n)
#define d3(x) (x+n+n)
struct edge{
    int from,to,w,nxt;
}e[5000000];
int head[500000],cnt=0;
void add(int u,int v,int w){
    e[++cnt]=(edge){u,v,w,head[u]};
    head[u]=cnt;
}
int S,T;
int dis[500000]={0};
bool vis[500000]={false};
int spfa(){
    std::queue<int> q;
    memset(dis,-128,sizeof(dis));
    q.push(S);
    vis[S]=true;
    dis[S]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=false;
        for(int i=head[x];i;i=e[i].nxt){
            if(dis[e[i].to]<dis[x]+e[i].w){
                dis[e[i].to]=dis[x]+e[i].w;
                if(!vis[e[i].to]){
                    vis[e[i].to]=true;
                    q.push(e[i].to);
                }
            }
        }
    }
    return dis[T];
}
int w[500000];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=m;i++){
        int u,v,z;
        scanf("%d%d%d",&u,&v,&z);
        add(d1(u),d1(v),0);
        add(d2(u),d2(v),0);
        add(d3(u),d3(v),0);
        add(d1(u),d2(v),-w[u]);
        add(d2(u),d3(v),w[u]);
        if(z==2){
            add(d1(v),d1(u),0);
            add(d2(v),d2(u),0);
            add(d3(v),d3(u),0);
            add(d1(v),d2(u),-w[v]);
            add(d2(v),d3(u),w[v]);
        }
    }
    S=d1(1);
    T=d3(n)+1;
    add(d1(n),T,0);
    add(d3(n),T,0);
    printf("%d\n",spfa());
    return 0;
}