求调

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int c[N],a[N];
int dfn[N],low[N];
int stac[N],ins[N];
vector<int> g[N];
vector<int> sc[N];
int num,cnt,top;
int mxn[N],mnn[N];
vector<int> g1[N];
vector<int> g2[N];
int f[N],w[N];

void tarjan(int x)
{
	dfn[x] = low[x] = ++num;
	stac[++top] = x;
	ins[x] = 1;
	for (int v : g[x])
	{
		if (!dfn[v])
		{
			tarjan(v);
			low[x] = min(low[x],low[v]);
		}
		else if (ins[v])
			low[x] = min(low[x],dfn[v]);
	} 
	if (dfn[x] == low[x])
	{
		cnt++;
		int y;
		do
		{
			y = stac[top--];
			ins[y] = 0;
			c[y] = cnt;
			sc[cnt].push_back(y);
		} while (x != y);
	}
}

void dfs(int u)
{
	for (int v : g1[u])
	{
		w[v] = min(w[u],mnn[v]);
		dfs(v);
	}
}

void dfs1(int u)
{
	for (int v : g2[u])
	{
		f[v] = max(f[u],mxn[v]);
		dfs1(v);
	}
}

int main()
{
	int n,m;
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];
		
	for (int i = 1; i <= m; i++)
	{
		int u,v,op;
		cin >> u >> v >> op;
		
		g[u].push_back(v);
		if (op == 2)
			g[v].push_back(u);
	}
	
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			tarjan(i);
	
	for (int i = 1; i <= cnt; i++)
	{
		int mx = 0,mn = INT_MAX;
		for (int j = 0; j < sc[i].size(); j++)
		{
			mx = max(mx,a[sc[i][j]]);
			mn = min(mn,a[sc[i][j]]);
		}
		mxn[i] = mx;
		mnn[i] = mn;
	} 

	for (int i = 1; i <= n; i++)
	{
		for (int v : g[i])
		{
			if (c[i] == c[v])
				continue;
			g1[c[i]].push_back(c[v]);
			g2[c[v]].push_back(c[i]);
		}
	}
	
	memset(w,0x3f,sizeof w);
	w[c[1]] = mnn[c[1]];
	f[c[n]] = mxn[c[n]];
	
	dfs(c[1]);
	dfs1(c[n]);
	
	int ans = 0;
	for (int i = 1; i <= cnt; i++)
		ans = max(ans,f[i] - w[i]);
	cout << ans;
}