记录编号	21998	评测结果	AAAAAEEEEA
题目名称	城市	最终得分	60
用户昵称	belong.zmx	是否通过	未通过
代码语言	Pascal	运行时间	1.257 s
提交时间	2010-11-16 14:48:11	内存使用	106.17 MiB

program cost(input,output);
var
 n,m:longint;
 u,v,s:longint;
 w:array[1..35000]of longint;
 a:array[1..3500,1..3500]of longint;
 i,j:longint;
 f:array[1..3500,0..3500]of longint;
 x,y,z:longint;
 t:array[1..3500,0..3500]of boolean;
 q:array[1..100000,1..2]of longint;
 head,tail,ans:longint;

function max(a,b:longint):longint;
begin
 if a>b then max:=a else max:=b;
end;

function min(a,b:longint):longint;
begin
 if a>b then min:=b else min:=a;
end;

begin
 assign(input,'cost.in');
 reset(input);
 readln(n,m,u,v,s);
 for i:=1 to n do
  for j:=1 to s do
   f[i,j]:=maxlongint;
 for i:=1 to n do
  for j:=1 to n do
  begin
   a[i,j]:=maxlongint;
  end;
 for i:=1 to n do readln(w[i]);
 for i:=1 to m do
 begin
  readln(x,y,z);
  a[x,y]:=min(z,a[x,y]);
  a[y,x]:=min(z,a[y,x]);
 end;
 close(input);

 head:=1;
 tail:=1;
 q[head,1]:=u;
 q[head,2]:=0;
 f[u,0]:=w[u];
 t[u,0]:=true;
 repeat
  for i:=1 to n do
   if (a[q[head,1],i]<maxlongint)and(f[i,q[head,2]+a[q[head,1],i]]>max(f[q[head,1],q[head,2]],w[i])) then
   begin
    if t[i,q[head,2]+a[q[head,1],i]]=true then
    begin
     f[i,q[head,2]+a[q[head,1],i]]:=max(f[q[head,1],q[head,2]],w[i]);
    end
    else
    begin
     inc(tail);
     q[tail,1]:=i;
     q[tail,2]:=q[head,2]+a[q[head,1],i];
     f[i,q[head,2]+a[q[head,1],i]]:=max(f[q[head,1],q[head,2]],w[i]);
     t[i,q[head,2]+a[q[head,1],i]]:=true;
    end;
   end;
  t[q[head,1],q[head,2]]:=false;
  inc(head);
 until head>tail;

 ans:=maxlongint;
 for i:=s downto 1 do
  if f[v,i]<ans then ans:=f[v,i];

 assign(output,'cost.out');
 rewrite(output);
 if (ans=maxlongint)or(v>n) then writeln('-1')
  else writeln(ans);
 close(output);
end.