比赛 不平凡的世界 评测结果 AAAWWAAAAA
题目名称 不平凡的引线 最终得分 80
用户昵称 Derrick_M 运行时间 0.805 s
代码语言 Pascal 内存使用 4.10 MiB
提交时间 2015-11-05 09:10:42
显示代码纯文本
program P2095;
type
  roads=record
  toit,next,val:longint;
end;
var
  road:array[1..200010] of roads;
  min1,min2,minn,list,a:array[1..100010] of longint;
  leaf,flag:array[1..100010] of boolean;
  max0,ans,n,m,i,u,v,w,root,cnt:longint;

procedure add(u,v,w:longint);
begin
  inc(cnt);
  road[cnt].toit:=v;
  road[cnt].next:=list[u];
  road[cnt].val:=w;
  list[u]:=cnt;
  inc(a[v]);
end;

procedure dfs(u:longint);
var
  v,w:longint;
begin
  flag[u]:=true;
  if leaf[u] then
  begin
    min1[u]:=0;
    exit;
  end;
  w:=list[u];
  while w<>0 do
  begin
    v:=road[w].toit;
    if not flag[v] then
    begin
      dfs(v);
      if min1[u]>min1[v]+road[w].val then
      begin
        min2[u]:=min1[u];
        min1[u]:=min1[v]+road[w].val;
        minn[u]:=v;
      end
      else
        if min2[u]>min1[v]+road[w].val then
          min2[u]:=min1[v]+road[w].val;
    end;
    w:=road[w].next;
  end;
end;

function getmin(u,v:longint):longint;
begin
  if u<v then exit(u)
         else exit(v);
end;

procedure work(u,v0:longint);
var
  v,w,min:longint;
begin
  flag[u]:=true;
  w:=list[u];
  if leaf[u] then
  begin
    if v0>ans then ans:=v0;
    exit;
  end;
  while w<>0 do
  begin
    v:=road[w].toit;
    if not flag[v] then
    begin
      if minn[u]=v then min:=min2[u]
                   else min:=min1[u];
      work(v,getmin(min,v0)+road[w].val);
    end;
    w:=road[w].next;
  end;
end;

begin
  assign(input,'firelead.in');assign(output,'firelead.out');
  reset(input);rewrite(output);
  readln(m);
  n:=m+1;
  for i:=1 to m do
  begin
    readln(u,v,w);
    add(u,v,w);
    add(v,u,w);
  end;
  fillchar(leaf,sizeof(leaf),false);
  for i:=1 to n do
    if a[i]=1 then leaf[i]:=true
              else root:=i;
  fillchar(min1,sizeof(min1),$6F);
  fillchar(min2,sizeof(min2),$6F);
  fillchar(max0,sizeof(max0),$6F);
  dfs(root);
  fillchar(flag,sizeof(flag),false);
  ans:=0;
  work(root,max0);
  writeln(ans/2:0:1);
  close(input);close(output);
end.