记录编号	14846	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	chengyang	是否通过	通过
代码语言	Pascal	运行时间	0.409 s
提交时间	2009-11-05 17:01:46	内存使用	25.96 MiB

program heat;
var
  a:array[-1..2600,-1..2600]of longint;
  b:array[-1..2600]of int64;
  f:array[-1..2600]of boolean;
  i,j,k,n,m,u,v,s,e,min:longint;
begin
  assign(input,'heatwvx.in');
  assign(output,'heatwvx.out');
  reset(input); rewrite(output);
  readln(m,n,s,e);

  for i:=0 to m do begin
    b[i]:=9999999;
    f[i]:=true;
    for j:=0 to m do a[i,j]:=999999999;
  end;
  for i:=1 to n do begin
    readln(u,v,j);
    a[u,v]:=j;
    a[v,u]:=j;
  end;

  f[s]:=false;
  for i:=1 to m-1 do begin
    k:=1;
    min:=999999999;
    for j:=1 to m do begin
      if (f[j])and(a[s,j]<=min) then
       begin
        k:=j;
        min:=a[s,j];
       end;
    end;
    f[k]:=false;
    for v:=1 to m do if (a[s,v]>=a[s,k]+a[k,v])and(f[v]) then a[s,v]:=a[s,k]+a[k,v];
  end;

  writeln(a[s,e]);
  close(input); close(output);
end.