如果这题没有环，可以DFS每个点向后走所能找到的最大价格max[i]。

但是存在环，一次DFS不能使环上所有点的max[i]都能达到真实值

但是每个环上都有至少一个点达到真实值了，只要再搜一遍就可以完成max的统计

答案为max[i]-price[i]的最大值

可是除了前两个点过了，后面不是99就是98..可是正解都不超过20

到底哪里出问题了？

下面是程序：

program trade;

const maxn=100000;maxm=500000;

type

pointer=^node;

node=record

order:longint;

next:pointer;

end;

var

lj:array[1..maxn+100]of pointer;

p,max:array[1..maxn+100]of longint;

n,m:longint;

procedure ins(a,b:longint);

var

p:pointer;

begin

new(p);

p^.order:=b;

p^.next:=lj[a];lj[a]:=p;

end;

procedure init;

var

i,a,b,k:longint;

begin

readln(n,m);

for i:=1 to n do read(p[i]);

for i:=1 to n do max[i]:=p[i];

for i:=1 to m do begin

readln(a,b,k);

ins(a,b);

if k=2 then ins(b,a);

end;

end;

procedure search;

var

s,last:array[1..maxn+10]of longint;

use:array[1..maxn+10]of boolean;

k,now,l,top:longint;p:pointer;

begin

for k:=1 to n do use[k]:=false;

top:=1;s[1]:=1;last[1]:=0;

while top<>0 do begin

k:=s[top];l:=last[top];dec(top);

use[k]:=true;

if l<>0 then if max[k]>max[l] then max[l]:=max[k];

p:=lj[k];

while p<>nil do begin

now:=p^.order;

if not use[now] then begin

inc(top);s[top]:=now;last[top]:=k;

end

else if max[now]>max[k] then max[k]:=max[now];

p:=p^.next;

end;

end;

end;

procedure print;

var

i,ans:longint;

begin

ans:=0;

for i:=1 to n do if max[i]-p[i]>ans then ans:=max[i]-p[i];

writeln(ans);

end;

begin

init;

search;search;

print;

end.