我觉得没问题的，一测出来30分，求助各位大佬orz

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, m, a[N], dfn[N], cnt, t[N], id, mn[N], mx[N], ans1, ans2;
vector<int> g[N], ni[N], s[N]; //s为缩点后图连通情况 
bool vis[N], v[N];
void dfs(int x) {
	for(int i = 0;i < g[x].size();++i)
		if(!vis[g[x][i]]) {
			vis[g[x][i]] = true;
			dfs(g[x][i]);
		}
	dfn[++cnt] = x;
}
void dfs2(int x) {
	for(int i = 0;i < ni[x].size();++i)
		if(!vis[ni[x][i]]) {
			vis[ni[x][i]] = true;
			dfs2(ni[x][i]);
		}
	t[x] = id;
}
void dfs3(int x, int buy, int earn) {
	if(x == t[n]) {
		ans1 = max(ans1, earn);
		return;
	}
	for(int i = 0;i < s[x].size();++i) {
		if(!v[x]) {
			v[x] = true;
			dfs3(s[x][i], min(buy, mn[s[x][i]]), max(earn, mx[s[x][i]]-buy));
		}
	}
}
int main () {
	memset(mn, 0x3f, sizeof mn);
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;++i) scanf("%d", a+i);
	for(int i = 1, x, y, z;i <= m;++i) {
		scanf("%d%d%d", &x, &y, &z);
		g[x].push_back(y);
		ni[y].push_back(x);
		if(z == 2) g[y].push_back(x), ni[x].push_back(y);
	}
	for(int i = 1;i <= n;++i)
		if(!vis[i]) dfs(i);
	memset(vis, 0, sizeof vis);
	for(int i = cnt;i >= 1;--i)
		if(!vis[dfn[i]]) vis[dfn[i]] = true, ++id, dfs2(dfn[i]);
	for(int i = 1;i <= n;++i) {
		for(int j = 0;j < g[i].size();++j)
			if(t[i] != t[g[i][j]]) s[t[i]].push_back(t[g[i][j]]);
	}
	for(int i = 1;i <= id;++i) sort(s[i].begin(), s[i].end());
	for(int i = 1;i <= n;++i) {
		mn[t[i]] = min(mn[t[i]], a[i]);
		mx[t[i]] = max(mx[t[i]], a[i]);
		ans2 = max(ans2, mx[t[i]]-mn[t[i]]);
	}
	dfs3(1, mn[1], 0);
	printf("%d", max(ans1, ans2));
	return 0;
}