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.