记录编号	9981	评测结果	AAAAA
题目名称	医院设置	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2009-04-23 15:17:15	内存使用	0.16 MiB

program hospital;
var
  i,j,n:shortint;
  table:array [-1..100] of record
    p,l,r,v:longint;
    d:array [-1..100] of longint;
  end;
  f,flag:array [-1..100] of boolean;
  q:array [0..100] of shortint;
  tmp,sum:longint;
procedure init(no,step:integer);
begin
  table[1].d[no]:=step;f[no]:=true;
  if (table[no].d[table[no].l]=0) and not(f[table[no].l]) then init(table[no].l,step+1);
  if (table[no].d[table[no].r]=0) and not(f[table[no].r]) then init(table[no].r,step+1);
  if (table[no].d[table[no].p]=0) and not(f[table[no].p]) then init(table[no].p,step+1);
end;
procedure change(no:shortint;c:shortint);
var
  cv,t:integer;
begin
  fillchar (q,sizeof(q),0);
  fillchar (f,sizeof(f),0);
  f[c]:=true;
  cv:=1-table[c].d[no];table[c].d[no]:=1;
  q[0]:=1;q[1]:=no;f[no]:=true;
  while not(q[0]=0) do begin
    q[q[0]+1]:=-1;
    if (table[q[q[0]]].l<>c) and not(f[table[q[q[0]]].l]) and (table[q[q[0]]].l>0) then q[q[0]+1]:=table[q[q[0]]].l else
      if (table[q[q[0]]].r<>c) and not(f[table[q[q[0]]].r]) and (table[q[q[0]]].r<>0) then q[q[0]+1]:=table[q[q[0]]].r else
        if (table[q[q[0]]].p<>c) and not(f[table[q[q[0]]].p]) and (table[q[q[0]]].p<>0) then q[q[0]+1]:=table[q[q[0]]].p;
    if q[q[0]+1]<>-1 then begin
      inc(q[0]);
      f[q[q[0]]]:=true;
      inc(table[c].d[q[q[0]]],cv);
    end
    else dec(q[0]);
  end;
end;
procedure get(no:shortint);
var cp,cl,cr:shortint;
begin
  if flag[table[no].p] then table[no].d:=table[table[no].p].d else
    if flag[table[no].l] then table[no].d:=table[table[no].l].d else table[no].d:=table[table[no].r].d;
  table[no].d[no]:=0;
  if table[no].p<>0 then change(table[no].p,no);
  if table[no].l<>0 then change(table[no].l,no);
  if table[no].r<>0 then change(table[no].r,no);
end;
procedure find(no:integer);
begin
  f[no]:=true;
  if (flag[no]) then begin
    if (not(f[0])) and (table[no].l<>0) and not(f[table[no].l]) then find(table[no].l);
    if (not(f[0])) and (table[no].r<>0) and not(f[table[no].r]) then find(table[no].r);
    if (not(f[0])) and (table[no].p<>0) and not(f[table[no].p]) then find(table[no].p);
  end
  else begin
    tmp:=no;
    f[0]:=true;
  end;
end;
function judge:boolean;
var i:integer;
begin
  judge:=true;
  for i:=1 to n do if flag[i]=false then begin
    judge:=false;
    exit;
  end;
end;
begin
  fillchar (table,sizeof(table),$FF);
  fillchar (flag,sizeof(flag),0);
  assign (input,'hospital.in');
  reset (input);
  readln (n);
  for i:=1 to n do begin
    readln (table[i].v,table[i].l,table[i].r);
    if table[i].l<>0 then begin
      table[i].d[table[i].l]:=0;
      table[table[i].l].p:=i;
      table[table[i].l].d[i]:=0;
    end;
    if table[i].r<>0 then begin
      table[i].d[table[i].r]:=0;
      table[table[i].r].p:=i;
      table[table[i].r].d[i]:=0;
    end;
  end;
  close (output);
  assign (output,'hospital.out');
  rewrite (output);
  init(1,0);sum:=maxlongint;
  flag[1]:=true;
  while not(judge) do begin
    fillchar (f,sizeof(f),0);
    find(1);
    get(tmp);
    flag[tmp]:=true;
  end;
  for i:=1 to n do begin
    tmp:=0;
    for j:=1 to n do tmp:=tmp+table[i].d[j]*table[j].v;
    if tmp<sum then sum:=tmp;
  end;
  writeln (sum);
  close (output);
end.