ac1262.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

program tju1262;
const
  maxn=100000;
var
  v2,pre:array[0..maxn*2-3]of longint;
  len:array[0..maxn-2]of longint;
  last,down1,down2,down3,cbelow1,cbelow2,below,up,above:array[1..maxn]of longint;
  v:array[1..maxn]of boolean;
  n,i,x,y,ans:longint;
procedure cal_down(x:longint);
  var
    p,y,t:longint;
  begin
    v[x]:=true;p:=last[x];
    while p>=0 do begin
      y:=v2[p];
      if not v[y] then begin
        cal_down(y);

        t:=down1[y]+len[p shr 1];
        if t>down1[x] then begin down3[x]:=down2[x];down2[x]:=down1[x];down1[x]:=t;end
          else if t>down2[x] then begin down3[x]:=down2[x];down2[x]:=t;end
          else if t>down3[x] then down3[x]:=t;

        if below[y]>cbelow1[x] then begin cbelow2[x]:=cbelow1[x];cbelow1[x]:=below[y];end
          else if below[y]>cbelow2[x] then cbelow2[x]:=below[y];
      end;
      p:=pre[p];
    end;
    t:=down1[x]+down2[x];if t>cbelow1[x] then below[x]:=t else below[x]:=cbelow1[x];
  end;
procedure cal_up(x:longint);
  var
    p,y,t,tt:longint;
  begin
    v[x]:=true;p:=last[x];
    while p>=0 do begin
      y:=v2[p];
      if not v[y] then begin
        if down1[y]+len[p shr 1]=down1[x] then t:=down2[x] else t:=down1[x];
        if up[x]>t then t:=up[x];
        up[y]:=t+len[p shr 1];

        if below[y]=cbelow1[x] then above[y]:=cbelow2[x] else above[y]:=cbelow1[x];
        if above[x]>above[y] then above[y]:=above[x];
        t:=down1[y]+len[p shr 1];
        if t=down1[x] then begin t:=down2[x];tt:=down3[x];end
          else if t=down2[x] then begin t:=down1[x];tt:=down3[x];end
          else begin t:=down1[x];tt:=down2[x];end;
        if up[x]>tt then inc(t,up[x]) else inc(t,tt);
        if t>above[y] then above[y]:=t;

        t:=up[y]+down1[y]-len[p shr 1];
        if above[y]>t then t:=above[y];
        if below[y]>t then t:=below[y];
        if t<ans then ans:=t;

        cal_up(y);
      end;
      p:=pre[p];
    end;
  end;
begin
  repeat
    fillchar(last,sizeof(last),255);
    read(n,i);i:=0;
    repeat
      read(x,y,len[i shr 1]);
      v2[i]:=y;pre[i]:=last[x];last[x]:=i;inc(i);
      v2[i]:=x;pre[i]:=last[y];last[y]:=i;inc(i);
    until i>n*2-3;

    fillchar(down1,sizeof(down1),0);
    fillchar(down2,sizeof(down2),0);
    fillchar(down3,sizeof(down3),0);
    fillchar(cbelow1,sizeof(cbelow1),0);
    fillchar(cbelow2,sizeof(cbelow2),0);
    fillchar(below,sizeof(below),0);
    fillchar(v,sizeof(v),0);
    fillchar(up,sizeof(up),0);
    fillchar(above,sizeof(above),0);
    cal_down(1);
    ans:=maxlongint;
    fillchar(v,sizeof(v),0);
    cal_up(1);
    writeln(ans);
  until seekeof;
end.