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

program xmz;
var
f1,f2:text;
f:array[1..2500,1..2500]of integer;
d:array[1..2500]of longint;
y:array[1..2500]of boolean;
t1,t2,n,nn,x,e,a,min:longint;
begin
assign(f1,'heatwvx.in');assign(f2,'heatwvx.out');
reset(f1);rewrite(f2);
read(f1,n,nn,x,e);
for a:=1 to nn do
 begin
 read(f1,t1,t2);
 read(f1,f[t1,t2]);
 f[t2,t1]:=f[t1,t2];
 end;
 for a:=1 to n do
  d[a]:=99999999;d[x]:=0;

 repeat
  y[x]:=true;
  for a:=1 to n do if (not y[a])and(f[x,a]<>0)and(f[x,a]+d[x]<d[a])then
   d[a]:=f[x,a]+d[x];
  min:=99999999;
  for a:=1 to n do if (d[a]<min)and(not y[a]) then begin min:=d[a];x:=a;end;
 until min=99999999;
 writeln(f2,d[e]);
close(f1);close(f2);
end.