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

program dijiesitela;
var
  a:array[1..2500] of longint;
  n,k,m,j,u,w,b,c,i,min,p:longint;
  biaozhi:array[1..2500]of boolean;
  z:boolean;
  jilu:array[1..2500,1..2500]of longint;
begin
  assign (input,'heatwvx.in');
  reset (input);
  assign (output,'heatwvx.out');
  rewrite (output);
  readln (k,n,m,u);
  for i:=1 to n do
  begin
    readln (w,b,c);
    jilu[w,b]:=c;
    jilu[b,w]:=c
  end;
  for i:=1 to k do
    a[i]:=maxlongint;
  a[m]:=0;
  for i:=1 to k do
    biaozhi[i]:=false;
  for j:=1 to k-1 do
  begin
    min:=maxlongint;
    for i:=1 to k do
      if (biaozhi[i]=false)and(a[i]<min) then
      begin
        min:=a[i];
        p:=i;
      end;
    biaozhi[p]:=true;
    for i:=1 to k do
      if (jilu[p,i]>0)and(jilu[p,i]+a[p]<a[i]) then
        a[i]:=jilu[p,i]+a[p]
  end;
  writeln (a[u]);
  close (input);
  close (output)
end.