记录编号	7711	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 牧场旅行	最终得分	100
用户昵称	MayLava	是否通过	通过
代码语言	Pascal	运行时间	0.378 s
提交时间	2008-11-11 13:33:53	内存使用	11.57 MiB

program MayLava;

var
 dist,map,way:array[1..1000,0..1000]of longint;
 qq:array[0..1000]of boolean;
 n,m:longint;

procedure SPFA(o:longint);
 var
  q:array[0..1000]of longint;
  v:array[0..1000]of boolean;
  i,h,t,x:longint;
 begin
  fillchar(q,sizeof(q),0);
  fillchar(v,sizeof(v),false);
  h:=0;
  t:=0;
  for i:=1 to n do
   dist[o,i]:=maxlongint;
  inc(t);
  q[t]:=o;
  v[o]:=true;
  dist[o,o]:=0;
  while not(h=t) do begin
   h:=(h+1) mod n;
   x:=q[h];
   v[x]:=false;
   for i:=1 to map[x,0] do
    if (way[x,i]>0) and (dist[o,x]+way[x,i]<dist[o,map[x,i]]) then begin
     dist[o,map[x,i]]:=dist[o,x]+way[x,i];
     if not(v[map[x,i]]) then begin
      t:=(t+1)mod n;
      q[t]:=map[x,i];
      v[map[x,i]]:=true;
     end;
    end;
  end;
 end;

procedure floyd;
 var
  i,j,k:longint;
 begin
  for k:=1 to n do
   for i:=1 to n do
    for j:=1 to n do
     if (map[i,k]+map[k,j]<map[i,j]) then map[i,j]:=map[i,k]+map[k,j];
 end;

procedure main;
 var
  fin,fout:text;
  i,j,x,y,z:longint;
 begin
  assign(fin,'pwalk.in');
  reset(fin);
  assign(fout,'pwalk.out');
  rewrite(fout);
  fillchar(qq,sizeof(qq),true);
  fillchar(way,sizeof(way),0);
  readln(fin,n,m);
  for i:=1 to n do
   map[i,0]:=0;
  for i:=1 to n-1 do begin
   readln(fin,x,y,z);
   inc(map[x,0]);
   map[x,map[x,0]]:=y;
   way[x,map[x,0]]:=z;
   inc(map[y,0]);
   map[y,map[y,0]]:=x;
   way[y,map[y,0]]:=z;
  end;
  for i:=1 to m do begin
   readln(fin,x,y);
   if qq[x] then begin SPFA(x); qq[x]:=false; end;
   writeln(fout,dist[x,y]);
  end;
  close(fin);
  close(fout);
 end;

BEGIN
 main;
END.