求大佬指点求求求

万分感谢

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
inline int read(){
    int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}
int n, m;
struct edge{
	int u, v, nxt;
}e[maxn], e2[maxn];
int head[maxn], cnt, head2[maxn], cnt2;
void add(int u, int v) {
	e[++cnt] = { u, v, head[u] };
	head[u] = cnt;
}
void add2(int u, int v) {
	e2[++cnt2] = { u, v, head2[u] };
	head2[u] = cnt2;
} 
int c[maxn], minc[maxn], maxc[maxn], dfn[maxn], low[maxn], s[maxn], top, vis[maxn], tme, pd[maxn];
int flag, flag2;
vector<int> sd[maxn];
int tot;
void tarjan(int x) {
	low[x] = dfn[x] = ++tme;
	s[++top] = x, vis[x] = 1;
	for (int i = head[x]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v]) low[x] = min(low[x], dfn[v]);
	}
	if (dfn[x] == low[x]) {
		tot++;
		sd[tot].push_back(x);
		maxc[tot] = max(maxc[tot], c[x]);
		minc[tot] = min(minc[tot], c[x]);
		pd[x] = tot;
		vis[x] = 0;
		if (x == n) flag = tot;
		if (x == 1) flag2 = tot;
		while (s[top] != x) {
			pd[s[top]] = tot;
			sd[tot].push_back(s[top]);
			maxc[tot] = max(maxc[tot], c[s[top]]);
			minc[tot] = min(minc[tot], c[s[top]]);
			vis[s[top]] = 0;
			if (s[top] == n) flag = tot;
			if (s[top] == 1) flag2 = tot;
			top--;
		}
		top--;
	}
}
int minn = 0x3f3f3f3f, ans[maxn];
void dfs(int x, int fa) {
	minn = min(minn, minc[x]);
	ans[x] = max(ans[fa], maxc[x] - minn);
	for (int i = head2[x]; i; i = e2[i].nxt) {
		int y = e2[i].v;
		if (y == fa) continue;
		dfs(y, x);
	}
}
signed main(){
	n = read(), m = read();
	memset(minc, 0x3f, sizeof(minc));
	for (int i = 1; i <= n; i++) c[i] = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read(), opt = read();
		if (opt == 1) add(u, v);
		if (opt == 2) add(u, v), add(v, u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
//	for (int i = 1; i <= tot; i++) {
//		cout << i << ": ";
//		for (int j = 0; j < sd[i].size(); j++) 
//			cout << sd[i][j] << " ";
//		cout << endl;
//	}
	for (int i = 1; i <= tot; i++) {
		for (int j = 0; j < sd[i].size(); j++) {
			for (int k = head[sd[i][j]]; k; k = e[k].nxt) {
				int y = e[k].v;
				if (pd[y] == i) continue;
				add2(pd[y], i);
			}
		}
	}

//	for (int i = 1; i <= tot; i++) {
//		cout << i << " --> ";
//		for (int j = head2[i]; j; j = e2[j].nxt) 
//			cout << e2[j].v << " ";
//		cout << endl;
//	}
//	cout << flag << " " << flag2;
	dfs(flag, 0);
	cout << ans[flag2];
}