有亿点长

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

vector<int> G[MAXN], rG[MAXN];
int price[MAXN], min_price[MAXN], max_price[MAXN];
bool vis[MAXN];

void spfa_min(int start, int n) {
fill(min_price, min_price + n + 1, INF);
queue<int> q;
q.push(start);
min_price[start] = price[start];
vis[start] = true;

while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = false;
    for (int v : G[u]) {
        if (min_price[v] > min(min_price[u], price[v])) {
            min_price[v] = min(min_price[u], price[v]);
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

}

void spfa_max(int start, int n) {
fill(max_price, max_price + n + 1, -INF);
queue<int> q;
q.push(start);
max_price[start] = price[start];
vis[start] = true;

while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = false;
    for (int v : rG[u]) {
        if (max_price[v] < max(max_price[u], price[v])) {
            max_price[v] = max(max_price[u], price[v]);
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i++) {
    cin >> price[i];
}

for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    G[x].push_back(y);
    rG[y].push_back(x);
    if (z == 2) {
        G[y].push_back(x);
        rG[x].push_back(y);
    }
}

spfa_min(1, n);
spfa_max(n, n);

int ans = 0;
for (int i = 1; i <= n; i++) {
    if (min_price[i] != INF && max_price[i] != -INF) {
        ans = max(ans, max_price[i] - min_price[i]);
    }
}

cout << ans << endl;
return 0;

}