tarjan + topsort(就是个DAG上的dp）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int price[100010];
struct node
{
int point;
int nxt;
};
node l1[1000010],l2[1000010];
int h1[100010],h2[100010];
int t1,t2;
int tie;
int dfn[100010],low[100010];
bool instack[100010];
int top,stack[100010];
int belong[100010];
int bcnt;
int maxn[100010],minn[100010];
int ans[100010];
int in[100010];
bool could[100010];
int s[100010],t;
void add1(int x,int y)
{
l1[++t1].point=y;
l1[t1].nxt=h1[x];
h1[x]=t1;
}
void add2(int x,int y)
{
l2[++t2].point=y;
l2[t2].nxt=h2[x];
h2[x]=t2;
}
void tarjan(int x)
{
stack[++top]=x;
instack[x]=true;
low[x]=dfn[x]=++tie;
for(int i=h1[x];i;i=l1[i].nxt)
{
int net=l1[i].point;
if(!dfn[net])
{
tarjan(net);
if(low[net]<low[x])
low[x]=low[net];
}
else
if(instack[net]&&dfn[net]<low[x])
low[x]=dfn[net];
}
if(dfn[x]==low[x])
{
bcnt+=1;
int pass;
do
{
pass=stack[top];
top-=1;
belong[pass]=bcnt;
maxn[bcnt]=max(maxn[bcnt],price[pass]);
minn[bcnt]=min(minn[bcnt],price[pass]);
instack[pass]=false;
}while(pass!=x);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
minn[i]=0x7fffffff;
for(int i=1;i<=n;i++)
scanf("%d",&price[i]);
int a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add1(a,b);
if(c==2)
add1(b,a);
}
for(int i=1;i<=n;i++)
if(!belong[i])
tarjan(i);
for(int i=1;i<=n;i++)
{
for(int j=h1[i];j;j=l1[j].nxt)
if(belong[i]!=belong[l1[j].point])
{
in[belong[l1[j].point]]+=1;
add2(belong[i],belong[l1[j].point]);
}
}
if(in[belong[1]])
{
printf("0");
return 0;
}
for(int i=1;i<=bcnt;i++)
if(!in[i])
s[++t]=i;
could[belong[1]]=true;
int pass;
while(t)
{
pass=s[t];
t-=1;
if(could[pass])
ans[pass]=max(ans[pass],maxn[pass]-minn[pass]);
for(int i=h2[pass];i;i=l2[i].nxt)
{
int net=l2[i].point;
could[net]=max(could[net],could[pass]);
if(could[net])
{
minn[net]=min(minn[net],minn[pass]);
ans[net]=max(ans[pass],ans[net]);//dp转移
}
in[net]-=1;
if(!in[net])
s[++t]=net;
}
}
printf("%d",ans[belong[n]]);
}