建立正反图,枚举每个点为终点,正图算出到这个点最小购入价格,反图算出到这个点最大卖出价格,枚举以每个点为终点两者相减的价格更新最大值

#include<bits/stdc++.h>
// #define int long long //memset数组为0x3f时自觉去掉
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define ULL unsigned long long
#define PIII tuple<int,int,int>
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  100000 + 10,M = 2 * 500000 + 10;

int n,m;
int w[N];
bool vis[N];
int dmin[N],dmax[N];
vector<int> Gmin[M],Gmax[M];
void Spfa(vector<int> G[],int dist[],int type)
{
    queue<int> q;
    if(type == 0)
    {
        memset(dist,0x3f,sizeof dmin);
        q.push(1);
        dist[1] = w[1];
        vis[1] = 1;
    }
    else
    {
        memset(dist,-0x3f,sizeof dmax);
        q.push(n);
        dist[n] = w[n];
        vis[n] = 1;
    }

    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int v : G[u])
        {
            if(type == 0 && min(dist[u],w[v]) < dist[v] || type == 1 && max(dist[u],w[v]) > dist[v])
            {
                if(type == 0) dist[v] = min(dist[u],w[v]);
                else dist[v] = max(dist[u],w[v]);
                if(vis[v]) continue;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> w[i];
    while(m--)
    {
        int x,y,z;
        cin >> x >> y >> z;
        Gmin[x].emplace_back(y);
        Gmax[y].emplace_back(x);
        if(z == 2)
        {
            Gmin[y].emplace_back(x);
            Gmax[x].emplace_back(y);
        }
    }

    Spfa(Gmin,dmin,0);
    Spfa(Gmax,dmax,1);

    int ans = 0;
    for(int i=1;i<=n;i++) ans = max(dmax[i] - dmin[i],ans);

    cout << ans;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2025.02.14 14:40:56
 */