PWALK - Dạo chơi đồng cỏ

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=1000;
var
  a,c,d:array[1..MAXN,1..MAXN] of longint;
  xet,queue,deg:array[1..MAXN] of longint;
  f1,f2:text;
  q,n:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i,u,v:longint;
begin
  read(f1,n,q);
  for i:=1 to n-1 do
    begin
      read(f1,u,v,c[u,v]);
      c[v,u]:=c[u,v];
      inc(deg[u]); a[u,deg[u]]:=v;
      inc(deg[v]); a[v,deg[v]]:=u;
    end;
end;
procedure ans;
var
  i,u,v:longint;
begin
  for i:=1 to q do
    begin
      read(f1,u,v);
      writeln(f2,d[u,v]);
    end;
end;
procedure bfs(start:longint);
var
  first,last,u,i,v:longint;
begin
  first:=1; last:=1; queue[1]:=start;
  fillchar(xet,sizeof(xet),0);
  xet[start]:=1;
  while first<=last do
    begin
      u:=queue[first]; inc(first);
      for i:=1 to deg[u] do
        begin
          v:=a[u,i];
          if xet[v]=0 then
            begin
              xet[v]:=1;
              inc(last); queue[last]:=v;
              d[start,v]:=d[start,u]+c[u,v];
            end;
        end;
    end;
end;
procedure solve;
var
  i:longint;
begin
  for i:=1 to n do
    bfs(i);
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download