显然是一道最短路径的题目，但是
1 ≤ n ≤ 100000, 0 ≤ m ≤ 1000000能轻松打爆dij+heap
怎么办？
挖掘题意，这是一个DAG图（有向无环图）
所以对于此类问题，我们有特殊的作法
对于DAG，拓扑序列在前的点的最短路一定会被先更新（值得思考）
所以我们只用对DAG做一次拓扑，然后依次更新最短路即可；（其实很像dp）
多个入度为0的点不影响结果；
再回到这题，由于给出的是点的权值
可以考虑拆点，将点i拆成点i1,i2，i1,i2之间连一条指向i2的有向边，权值为原先点的权值
原先所有入边连向i1，出边连i2，权值都是0，这样就搞定了
拆点的做法在后面的网络流中会经常用到（当然这题也可以不拆）
type link=^node;
node=record
po,len:longint;
next:link;
end; var w:array[..] of link;
v:array[..] of boolean;
c,r,q,d:array[..] of longint;
n,m,ans,i,t,f,s,x,y:longint;
p,g:link;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure add(x,y,z:longint); //邻接表
var p:link;
begin
new(p);
p^.po:=y;
p^.len:=z;
p^.next:=w[x];
w[x]:=p;
end; begin
while not eoln do
begin
readln(n,m);
for i:= to *n do
w[i]:=nil;
fillchar(r,sizeof(r),);
fillchar(c,sizeof(c),);
for i:= to n do //拆点
begin
readln(x);
add(i+n,i,x);
inc(r[i]);
inc(c[i+n]);
end;
for i:= to m do //建边
begin
readln(x,y);
add(x,y+n,);
inc(r[y+n]);
inc(c[x]);
end;
s:=;
fillchar(v,sizeof(v),false);
fillchar(q,sizeof(q),);
for i:= to *n do //先找入度为0的点
if r[i]= then
begin
inc(s);
v[i]:=true;
q[s]:=i;
end;
f:=;
while s<*n do //生成拓扑序列
begin
inc(f);
p:=w[q[f]];
while p<>nil do
begin
dec(r[p^.po]);
if r[p^.po]= then
begin
inc(s);
q[s]:=p^.po;
end;
p:=p^.next;
end;
end;
for i:= to *n do //d[i]表示从某个入度为0的点到达当前点的最大距离
if v[i] then d[i]:= else d[i]:=-;
ans:=-;
for i:= to *n do
begin
f:=q[i];
p:=w[f];
g:=nil;
while p<>nil do //按照拓扑序列依次更新所有到达的点
begin
t:=p^.po;
d[p^.po]:=max(d[p^.po],d[f]+p^.len);
g:=p;
p:=p^.next;
dispose(g); //注意这题多测加上巨大的n，m很有可能把链表挤爆，所以及时释放掉空间
end;
end;
for i:= to *n do
if c[i]= then ans:=max(d[i],ans);
writeln(ans);
end;
end.
拓扑序列复杂度O(m)，最短路O(m)
所以总的复杂度O(m)