思路是 tarjan 缩点和拓扑

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 100001

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

std::vector<int> G[MAXN];
std::queue<int> q;
int n, m, pthn, head[MAXN], e[MAXN << 3][3], f[MAXN], g[MAXN], rd[MAXN];
int t, sc, cnt, s[MAXN], dfn[MAXN], low[MAXN], num[MAXN], a[MAXN];
bool vis[MAXN];
struct Edge {
	int next, to;
}pth[MAXN << 4];

void add(int from, int to) {
	pth[++pthn].to = to, pth[pthn].next = head[from];
	head[from] = pthn;
}

void tarjan(int u) {
	dfn[u] = low[u] = ++cnt;
	vis[u] = true, s[++sc] = u;
	for (int i = head[u]; i; i = pth[i].next) {
		int x = pth[i].to;
		if (!dfn[x]) {
			tarjan(x);
			low[u] = min(low[u], low[x]);
		}
		else if (vis[x]) low[u] = min(low[u], dfn[x]);
	}
	if (dfn[u] == low[u]) {
		int pre = -1;
		f[++t] = 0, g[t] = 2147483647;
		while (pre != u) {
			pre = s[sc--];
			vis[pre] = false;
			num[pre] = t;
			f[t] = max(f[t], a[pre]);
			g[t] = min(g[t], a[pre]);
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for (int i = 1; i <= m; ++i) {
		scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);
		add(e[i][0], e[i][1]);
		if (e[i][2] == 2) add(e[i][1], e[i][0]);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) tarjan(i);
	}
	for (int i = 1; i <= m; ++i) {
		if (num[e[i][0]] != num[e[i][1]]) {
			G[num[e[i][0]]].push_back(num[e[i][1]]);
			++rd[num[e[i][1]]];
			if (e[i][2] == 2) {
				G[num[e[i][1]]].push_back(num[e[i][0]]);
				++rd[num[e[i][0]]];
			}
		}
	}
	for (int i = 1; i <= t; ++i) {
		if (rd[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int i = 0; i < G[u].size(); ++i) {
			int v = G[u][i];
			g[v] = min(g[v], g[u]);
			--rd[v];
			if (rd[v] == 0) q.push(v);
		}
	}
	int ans = 0;
	for (int i = 1; i <= t; ++i) {
		ans = max(ans, f[i] - g[i]);
	}
	std::cout << ans << '\n';
	return 0;
}