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

program ReLang;
var
  way:array[1..2500,1..2500] of integer;
  cost:array[1..2500] of longint;
  n,m,te,ts,t,i,r1,r2,r3,mini:integer;
  min:longint;
  arrive:array[1..2500] of boolean;
begin
  assign(input,'heatwvx.in');
  reset(input);
  assign(output,'heatwvx.out');
  rewrite(output);
  readln(n,m,ts,te);
  fillchar(way,sizeof(way),0);
  fillchar(cost,sizeof(cost),0);
  fillchar(arrive,sizeof(arrive),false);
  for i:=1 to m do
  begin
    readln(r1,r2,r3);
    way[r1,r2]:=r3;
    way[r2,r1]:=r3
  end;
  arrive[ts]:=true;
  t:=ts;
  repeat
    for i:=1 to n do
    begin
      if way[t,i]>0 then
      begin
        if ((cost[t]+way[t,i]<cost[i]) or (cost[i]=0)) and (arrive[i]=false) then
        begin
          cost[i]:=cost[t]+way[t,i];
        end
      end
    end;
    min:=maxlongint;
    for i:=1 to n do
      if (arrive[i]=false) and (min>cost[i]) and (cost[i]>0) then
      begin
        min:=cost[i];
        mini:=i
      end;
    if min<maxlongint then
    begin
      arrive[mini]:=true;
      t:=mini;
    end
  until t=te;
  writeln(cost[te]);
  close(input);
  close(output)
end.