@[url=/space/show?uid=1]kkksc03[/url]

P1073 最优贸易

我把以前能做对这道题目的pascal程序，结果又出现了和楼上一样的情况，这次是80分

[codep]

type node=^tree;
tree=record d:longint;n:node;end;
var a,a_,b,b_:array[1..100000]of node;
c,c_:array[1..100000]of boolean;n,m,i,j,x,y,k:longint;
L,R,s:node;max,min,d:array[1..100000]of longint;bb:boolean;
procedure add(x,y:longint);
begin
  if c[x] then begin b[x]^.d:=y;new(b[x]^.n);b[x]:=b[x]^.n;b[x]^.n:=nil;b[x]^.d:=-1;end
  else begin new(a[x]);a[x]^.d:=y;new(a[x]^.n);b[x]:=a[x]^.n;b[x]^.n:=nil;b[x]^.d:=-1;end;
  c[x]:=true;
end;
procedure add_(x,y:longint);
begin
  if c_[x] then begin b_[x]^.d:=y;new(b_[x]^.n);b_[x]:=b_[x]^.n;b_[x]^.n:=nil;b_[x]^.d:=-1;end
  else begin new(a_[x]);a_[x]^.d:=y;new(a_[x]^.n);b_[x]:=a_[x]^.n;b_[x]^.n:=nil;b_[x]^.d:=-1;end;
  c_[x]:=true;
end;
begin
  read(n,m);for i:=1 to n do a[i]:=nil;
  for i:=1 to n do read(d[i]);
  for i:=1 to m do begin
    read(x,y,k);
    if k<2 then add(x,y)else begin add(x,y);add(y,x);end;
    if k<2 then add_(y,x)else begin add_(y,x);add_(x,y);end;
  end;
  new(l);r:=l;l^.n:=nil;l^.d:=1;bb:=true;fillchar(min,sizeof(min),1);min[1]:=d[1];
  while bb do begin
    s:=a[l^.d];
    if s<>nil then
    while s^.d<>-1 do begin
      if (min[s^.d]>d[s^.d])or(min[s^.d]>min[l^.d])
      then begin
        new(r^.n);r:=r^.n;r^.d:=s^.d;r^.n:=nil;
        if d[s^.d]>min[l^.d]then min[s^.d]:=min[l^.d]else min[s^.d]:=d[s^.d];
      end;
      s:=s^.n;
    end;
    if l=r then bb:=false else begin s:=l^.n;dispose(l);l:=s;end;
  end;dispose(l);
  new(l);r:=l;l^.n:=nil;l^.d:=n;bb:=true;fillchar(max,sizeof(max),0);max[n]:=d[n];
  while bb do begin
    s:=a_[l^.d];
    if s<>nil then
    while s^.d<>-1 do begin
      if (max[s^.d]<d[s^.d])or(max[s^.d]<max[l^.d])
      then begin
        new(r^.n);r:=r^.n;r^.d:=s^.d;r^.n:=nil;
        if d[s^.d]<max[l^.d]then max[s^.d]:=max[l^.d]else max[s^.d]:=d[s^.d];
      end;
      s:=s^.n;
    end;
    if l=r then bb:=false else begin s:=l^.n;dispose(l);l:=s;end;
  end;dispose(l);k:=0;
  for i:=1 to n do if max[i]-min[i]>k then k:=max[i]-min[i];
  writeln(k);
end.
[/codep]