30pts 求条

#include <bits/stdc++.h>
using namespace std;
const int N = 100005,M = 1000005;
int n,m,u,v,w,cnt,sum;
int dfn[N],low[N],f[N],tot;
int c[N],head[N],ver[M],nxt[M];
int head2[N],ver2[M],nxt2[M];
int deg[N],cnt2,res;
int mx[N],mn[N];
bool ins[N],vis[N];
stack<int> s;
queue<int> q;
void add(int x,int y)
{
	ver[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt; 
}
void add2(int x,int y)
{
	ver2[++cnt2] = y;
	nxt2[cnt2] = head2[x];
	head2[x] = cnt2; 
	deg[y]++;
}
void tarjan(int u)
{
	s.push(u); ins[u] = 1;
	dfn[u] = low[u] = ++tot;
	for (int i=head[u];i;i=nxt[i])
	{
		int v = ver[i];
		if (dfn[v] == 0)
		{
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}
		else if (ins[v]) low[u] = min(low[u],dfn[v]);
	}
	if (low[u] == dfn[u])
	{
		++sum;
		mx[sum] = mn[sum] = c[u];
		while (s.top() != u)
		{
			f[s.top()] = sum;
			ins[s.top()] = 0;
			mx[sum] = max(mx[sum],c[s.top()]);
			mn[sum] = min(mn[sum],c[s.top()]);
			s.pop();
		}
		f[s.top()] = sum;
		ins[s.top()] = 0;
		s.pop();
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&c[i]);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v);
		if (w == 2) add(v,u);
	}
	for (int i=1;i<=n;i++)
	{
		if (dfn[i]) continue;
		tarjan(i);
	}
	for (int u=1;u<=n;u++)
	{
		for (int i=head[u];i;i=nxt[i])
		{
			int v = ver[i];
			if (f[v] == f[u]) continue;
			add2(f[u],f[v]);
		}
	}
	q.push(f[1]);
	while (q.size())
	{
		int u = q.front();
		q.pop();
		vis[u] = 1;
		for (int i=head2[u];i;i=nxt2[i])
		{
			int v = ver2[i];
			deg[v]--;
			mn[v] = min(mn[v],mn[u]);
			if (deg[v] == 0) q.push(v);
		}
	}
	cnt2 = 0;
	memset(head2,0,sizeof(head2));
	memset(deg,0,sizeof(deg));
	for (int u=1;u<=n;u++)
	{
//		cout << u << ' ' << dfn[u] << ' ' << f[u] << ' ' << mx[f[u]] << ' ' << mn[f[u]] << endl;
		if (vis[f[u]] == 0) continue;
		for (int i=head[u];i;i=nxt[i])
		{
			int v = ver[i];
			if (f[v] == f[u]) continue;
			add2(f[v],f[u]);
		}
	}
	q.push(f[n]);
	while (q.size())
	{
		int u = q.front();
		q.pop();
		res = max(mx[u]-mn[u],res);
		for (int i=head2[u];i;i=nxt2[i])
		{
			int v = ver2[i];
			mx[v] = max(mx[v],mx[u]);
			deg[v]--;
			if (deg[v] == 0) q.push(v);
		}
	}
	printf("%d",res);
	return 0;
}