记录编号	14722	评测结果	AAAAAAAAAA
题目名称	[USACO Oct09] 热浪	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.714 s
提交时间	2009-11-03 17:08:36	内存使用	23.98 MiB

program heatwvx;
var
  table:array [0..2500,0..2500] of longint;
  dij:array [0..2500] of longint;
  flag:array [0..2500] of boolean;
  u,min,num,a,b,t,n,m,ts,te,i,j:longint;
begin
  fillchar (flag,sizeof(flag),0);
  fillchar (table,sizeof(table),$FF);
  for i:=0 to 2500 do dij[i]:=maxlongint;
  assign (input,'heatwvx.in');
  reset (input);
  readln (n,m,ts,te);
  for i:=1 to m do begin
    readln (a,b,t);
    table[a,b]:=t;
    table[b,a]:=t;
  end;
  dij[ts]:=0;num:=0;
  close (input);
  assign (output,'heatwvx.out');
  rewrite (output);
  while num<=n do begin
    inc(num);min:=maxlongint;
    for i:=1 to n do if (flag[i]=false) and (dij[i]<min) then begin
      min:=dij[i];
      u:=i;
    end;
    flag[u]:=true;
    for i:=1 to n do if (dij[u]+table[u,i]<dij[i]) and (table[u,i]>0) then dij[i]:=dij[u]+table[u,i];
  end;
  writeln (dij[te]);
  close (output);
end.