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

program ex;
type
 ss=array[1..2500,1..2500]of longint;
var
 map:ss;
 t,c,ts,te:longint;
procedure init;
 var
  i,j:integer;
  x,y,z:integer;
 begin
  assign(input,'heatwvx.in');
  assign(output,'heatwvx.out');
  reset(input);
  rewrite(output);
  readln(t,c,ts,te);
  for i:=1 to t do
   for j:=1 to t do
    map[i,j]:=2500000;
  for i:=1 to c do
   begin
    readln(x,y,z);
    map[x,y]:=z;
    map[y,x]:=z;
   end;
  close(input);
 end;
procedure dijk;
 var
  i,j:longint;
  num,min:longint;
  flag:array[1..2500]of boolean;
 begin
  fillchar(flag,sizeof(flag),false);
  flag[ts]:=true;
  num:=ts;
  for i:=1 to t do
   if i<>ts then
    begin
     min:=maxlongint;
     for j:=1 to t do
      if (map[ts,j]<min)and(flag[j]=false)and(j<>ts) then
       begin
        min:=map[ts,j];
        num:=j;
       end;
     flag[num]:=true;
     for j:=1 to t do
      if (j<>num)and(j<>ts)and(map[ts,num]+map[num,j]<map[ts,j])and(flag[j]=false) then
       map[ts,j]:=map[ts,num]+map[num,j];
    end;
 end;
begin
 init;
 dijk;
 writeln(map[ts,te]);
 close(output);
end.