ac1222.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1222;
const
  maxn=200000;
var
  e:array[0..maxn*2-2]of record v2,len,pre:longint;end;
  last,pe,q:array[1..maxn]of longint;
  v:array[1..maxn]of boolean;
  path:array[1..maxn]of record l1,l2,l3:int64;s1:longint;end;
  m,i,f,r,t:longint;
  l,ans:int64;
begin
  q[1]:=1;
  repeat
    fillchar(last,sizeof(last),0);
    fillchar(v,sizeof(v),0);
    fillchar(path,sizeof(path),0);

    read(m,m);
    for i:=1 to m do begin
      read(f,r,t);
      with e[i*2-1] do begin v2:=r;len:=t;pre:=last[f];end;last[f]:=i*2-1;
      with e[i*2] do begin v2:=f;len:=t;pre:=last[r];end;last[r]:=i*2;
    end;

    f:=0;r:=1;
    repeat
      inc(f);v[q[f]]:=true;t:=last[q[f]];
      while t>0 do begin
        if v[e[t].v2] then pe[q[f]]:=t else begin inc(r);q[r]:=e[t].v2;end;
        t:=e[t].pre;
      end;
    until f=r;

    for i:=f downto 1 do
      with path[q[i]] do
        while e[pe[q[r]]].v2=q[i] do begin
          l:=path[q[r]].l1+e[pe[q[r]]].len;
          if l>l1 then begin l3:=l2;l2:=l1;l1:=l;s1:=q[r];end
            else if l>l2 then begin l3:=l2;l2:=l;end
            else if l>l3 then l3:=l;
          dec(r);
        end;

    ans:=path[1].l1+path[1].l2*2+path[1].l3;
    for i:=2 to f do begin
      with path[e[pe[q[i]]].v2] do
        if s1=q[i] then l:=l2 else l:=l1;
      inc(l,e[pe[q[i]]].len);
      with path[q[i]] do begin
        if l>l1 then begin l3:=l2;l2:=l1;l1:=l;end
          else if l>l2 then begin l3:=l2;l2:=l;end
          else if l>l3 then l3:=l;
        l:=l1+l2*2+l3;if l>ans then ans:=l;
      end;
    end;
    writeln(ans);
  until seekeof;
end.