tarjan缩点+topu+dp
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#define maxn 1000001
using namespace std;
int n,m;
struct pp
{
int next,to;
}a1[maxn],a2[maxn];
int vis[maxn];
int into[maxn];
int w1[maxn],w2[maxn];
int maxx[maxn];
int head1[maxn],head2[maxn];
int t1,t2;
int price[maxn];
int x[maxn],y[maxn];
int color[maxn];
int dfn[maxn];
int num;
int dis[maxn];
int sum;
int low[maxn];
int dep[maxn];
int dp[maxn];
int minc[maxn];
int ans;
stack<int> s;
void add1(int u,int v)
{
a1[++t1].next=head1[u];
a1[t1].to=v;
head1[u]=t1;
}
void add2(int u,int v)
{
a2[++t2].next=head2[u];
a2[t2].to=v;
head2[u]=t2;
}
void tarjan(int x)
{
dfn[x]=low[x]=++num;
s.push(x);
vis[x]=1;
for(int i=head1[x];i;i=a1[i].next)
{
if(!dfn[a1[i].to])
{
tarjan(a1[i].to);
low[x]=min(low[x],low[a1[i].to]);
}
else
if(vis[a1[i].to])
{
low[x]=min(low[x],dfn[a1[i].to]);
}
}
if(dfn[x]==low[x])
{ sum++;
while(s.top()!=x)
{
vis[s.top()]=0;
color[s.top()]=sum;
s.pop();
}
vis[s.top()]=0;
color[s.top()]=sum;
s.pop();
}
return ;
}
void topu()
{
queue<int> q;
for(int i=1;i<=sum;i++)
{
if(!into[i])
q.push(i);
}
while(!q.empty())
{
int x=q.front();
q.pop();
dep[++ans]=x;
for(int i=head2[x];i;i=a2[i].next)
{
int v=a2[i].to;
into[a2[i].to]--;
if(into[v]==0)
q.push(v);
}
}
memset(minc,0x3f,sizeof(minc));
minc[dep[1]]=w2[dep[1]];
for(int i=1;i<=ans;i++)
{
int x=dep[i];
for(int j=head2[x];j;j=a2[j].next)
{
int u=a2[j].to;
minc[u]=min(minc[u],min(minc[x],w2[x]));
dp[u]=max(dp[u],max(dp[x],max(maxx[u],w1[u]-minc[u])));
}
}
cout<<dp[color[n]];
}
int main()
{
memset(w2,0x3f,sizeof(w2));
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>price[i];
for(int i=1;i<=m;i++)
{
int a,b,z;
cin>>a>>b>>z;
if(z==2)
{
add1(a,b);
add1(a,b);
}
if(z==1)
add1(a,b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;i++)
for(int j=head1[i];j;j=a1[j].next)
{
int u=a1[j].to;
if(color[i]!=color[u])
{
add2(color[i],color[u]);
into[color[u]]++;
}
}
for(int i=1;i<=n;i++)
{
w1[color[i]]=max(w1[color[i]],price[i]);
w2[color[i]]=min(w2[color[i]],price[i]);
}
for(int i=1;i<=sum;i++)
maxx[i]=w1[i]-w2[i];
topu();
return 0;
}
```
by Ruff @ 2018-07-24 21:31:46
@[Ruff](/space/show?uid=30205)
数据水被你水过去了
by henry_y @ 2018-07-24 21:49:33
@[henry_y](/space/show?uid=36526) 大犇请指教
by Ruff @ 2018-07-25 20:33:03
@[henry_y](/space/show?uid=36526) 你加双向边的时候加成了两个单向边
by 青珹 @ 2018-09-21 18:41:36
@[Ruff](/space/show?uid=30205) 抱歉，@ 错了……
by 青珹 @ 2018-09-21 19:37:40