题解

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 100005;
const int Maxm = 500005;
pair<int,int> q;
int n,m,size,cnt,sum,ans,Index,tot;
int f[Maxn],first[Maxn],First[Maxn],c[Maxn];
int low[Maxn],num[Maxn],father[Maxn],vis[Maxn],p[Maxn],maxx[Maxn];
struct shu
{
int to,next;
};
shu edge[Maxm<<1],Edge[Maxm<<1];
inline int get_int()
{
int x = 0,f = 1;
char c;
for (c = getchar();(!isdigit(c)) and (c != '-');c = getchar());
if (c == '-')
{
f = -1,c = getchar();
}
for ( ;isdigit(c);c = getchar())
{
x = (x<<3) + (x<<1) + c - '0';
}
return x * f;
}
inline void build(int x,int y)
{
edge[++size].next = first[x];
first[x] = size;
edge[size].to = y,edge[size];
}
inline void Build(int x,int y)
{
Edge[++size].next = First[x];
First[x] = size;
Edge[size].to = y,Edge[size];
}
inline void tarjan(int point)
{
low[point] = num[point] = ++Index;
vis[point] = 1,p[++tot] = point;
for(int u = first[point];u;u = edge[u].next)
{
int to = edge[u].to;
if (!num[to])
{
tarjan(to),low[point] = min(low[point],low[to]);
}
else if(vis[to])
{
low[point] = min(low[point],num[to]);

    }
}
if (low[point] == num[point])
{
	cnt++;
  	while(1)
  	{
  		int x = p[tot--];
  		vis[x] = 0,father[x] = cnt,maxx[cnt] = max(maxx[cnt],c[x]);
  		if (x == point)
        {
            break;
        }
  	}
}

}
inline void dfs(int point,int fa)
{
vis[point] = 1;
for (int u = First[point];u;u = Edge[u].next)
{
int to = Edge[u].to;
if(vis[to])
{
continue;
}
f[to] = max(maxx[to],f[point]);
dfs(to,point);
}
}
int main(void)
{
n = get_int(),m = get_int();
for (int i = 1;i <= n;i++)
{
c[i] = get_int();
}
for (int i = 1;i <= m;i++)
{
int x = get_int(),y = get_int(),z = get_int();
build(x,y);
if (z == 2)
{
build(y,x);
}
}
for (int i = 1;i <= n;i++)
{
if (!num[i])
{
tarjan(i);
}
}
for (int i = 1;i <= n;i++)
{
for (int u = first[i];u;u = edge[u].next)
{
if (father[edge[u].to] != father[i])
{
Build(father[edge[u].to],father[i]);
}
}
}
f[father[n]] = maxx[father[n]];
dfs(father[n],0);
for (int i = 1;i <= n;i++)
{
if (vis[father[i]])
{
ans = max(ans,f[father[i]] - c[i]);
}
}
cout << ans;
return 0;
}