f,x,xx,g,yy,ne,we:array[1..2,0..500000]of longint;
n,m,i,j,k,a,b,c,st,en,max:longint;
begin
assign(input,'trade.in');
assign(output,'trade.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do read(v[i]);
for i:=1 to m do
begin
inc(k);
readln(z[1],z[2],a);
for j:=1 to a do
begin
b:=z[j];c:=z[3-j];
if j=2 then inc(k);
if yy[1,b]=0 then begin yy[1,b]:=1;x[1,b]:=k;g[1,b]:=k;end
else begin ne[1,g[1,b]]:=k;g[1,b]:=k;end;
inc(xx[1,b]);
we[1,k]:=c;
if yy[2,c]=0 then begin yy[2,c]:=1;x[2,c]:=k;g[2,c]:=k;end
else begin ne[2,g[2,c]]:=k;g[2,c]:=k;end;
we[2,k]:=b;
inc(xx[2,c]);
end;
end;
for i:=1 to n do
begin
f[1,i]:=v[i];
f[2,i]:=v[i];
end;
for i:=1 to 2 do
begin
fillchar(y1,sizeof(y1),0);
fillchar(y2,sizeof(y2),0);
fillchar(d,sizeof(d),0);
st:=0;en:=1;
if i=1 then begin d[1]:=1;y2[1]:=1;f[i,1]:=10000;f[i,n]:=10000;end
else begin d[1]:=n;y2[n]:=1;f[i,n]:=0;f[i,1]:=0;end;
while st<>en do
begin
st:=(st mod n)+1;
a:=x[i,d[st]];
b:=we[i,a];
if i=1 then
begin
for j:=1 to xx[i,st] do
begin
if f[i,b]>f[i,d[st]] then
begin
f[i,b]:=f[i,d[st]];
if y1[b]=0 then begin en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;end;
end;
if (f[i,b]<=f[i,d[st]])and(y2[b]=0)then
begin
en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;
end;
a:=ne[i,a];
b:=we[i,a];
end;
end;
if i=2 then
begin
for j:=1 to xx[i,st] do
begin
if f[i,b]<f[i,d[st]] then
begin
f[i,b]:=f[i,d[st]];
if y1[b]=0 then begin en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;end;
end;
if (f[i,b]>=f[i,d[st]])and(y2[b]=0)then
begin
en:=(en mod n)+1;d[en]:=b;y1[b]:=1;y2[b]:=1;
end;
a:=ne[i,a];
b:=we[i,a];
end;
end;
y1[st]:=0;
end;
end;
max:=0;
for i:=2 to n-1 do
if max<f[2,i]-f[1,i] then max:=f[2,i]-f[1,i];
writeln(max);
readln;
close(input);
close(output);
end.
[color=red]
话说……悬赏什么滴太不真实了昂~你记个【注释:这个】程序似哪道题目呐~~看下题目,谢谢昂~
一般重赏下会有管理员来,然后让LZ自己思考不然把分就乱给
我不是那样的人~
http://www.rqnoj.cn/Discuss_Show.asp?DID=8986
某人的帖子
人品+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++