记录编号	33490	评测结果	AAAAAATTTA
题目名称	城市	最终得分	80
用户昵称	lizhe	是否通过	未通过
代码语言	Pascal	运行时间	3.063 s
提交时间	2011-11-10 19:47:48	内存使用	40.38 MiB

program cost;
const
  maxtin=500000;
var
  i,j,n,m,u,v,l,r,mid,x,y,z,head,tail,tt:longint;
  min1,min2,s,max:int64;
  a,num,t,b,d:array[1..10000]of longint;
  flag,ff:array[1..10000]of boolean;
  map,w:array[1..10000,1..500]of longint;
  que:array[1..maxtin]of longint;
procedure swap(var a0,b0:longint);
var
  c0:longint;
begin
  c0:=a0;
  a0:=b0;
  b0:=c0
end;

procedure sort(l,r:longint);
var
  i,j,x:longint;
begin
  i:=l;
  j:=r;
  x:=b[(l+r) div 2];
  repeat
    while b[i]<x do inc(i);
    while x<b[j] do dec(j);
    if i<=j then
    begin
      swap(b[i],b[j]);
      swap(num[i],num[j]);
      inc(i);
      dec(j);
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

procedure spfa(x,y:longint);
begin
  fillchar(flag,sizeof(flag),true);
  for i:=1 to n do d[i]:=maxlongint;
  d[x]:=0;
  flag[x]:=false;
  que[1]:=x;
  head:=0;
  tail:=1;
  while  (head<tail) and (tail<maxtin) do
  begin
    inc(head);
    for i:=1 to t[que[head]] do
      if (d[map[que[head],i]]>d[que[head]]+w[que[head],i]) and (a[map[que[head],i]]<=max) then
      begin
        d[map[que[head],i]]:=d[que[head]]+w[que[head],i];
        if flag[map[que[head],i]] then
        begin
          flag[map[que[head],i]]:=false;
          inc(tail);
          que[tail]:=map[que[head],i]
        end
      end;
    flag[que[head]]:=true
  end
end;

procedure init;
begin
  assign(input,'cost.in');
  reset(input);
  assign(output,'cost.out');
  rewrite(output);
  read(n,m,u,v,s);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do num[i]:=i;
  for i:=1 to m do
  begin
    read(x,y,z);
    inc(t[x]);
    map[x,t[x]]:=y;
    w[x,t[x]]:=z;
    inc(t[y]);
    map[y,t[y]]:=x;
    w[y,t[y]]:=z;
  end;
  max:=maxlongint;
  spfa(u,v);
  fillchar(ff,sizeof(ff),true);
  for i:=1 to n do
    if d[i]>=maxlongint then
      ff[i]:=false;
  spfa(v,u);
  for i:=1 to n do
    if d[i]>=maxlongint then
      ff[i]:=false;
  for i:=1 to n do
    if ff[i] then
    begin
      inc(tt);
      b[tt]:=a[i];
      num[tt]:=i
    end;
  sort(1,tt)
end;

function ok:boolean;
begin
  ok:=true;
  max:=b[mid];
  if (a[u]>max) or (a[v]>max) then exit(false);
  spfa(u,num[mid]);
  min1:=d[num[mid]];
  spfa(num[mid],v);
  min2:=d[v];
  if min1+min2>s then exit(false);
end;

procedure erfen;
begin
   l:=1; r:=tt;
   while l<r do
   begin
     mid:=(l+r) shr 1;
     if ok then r:=mid
     else l:=mid+1
   end;
   mid:=l;
   if ok then writeln(b[l])
   else writeln('-1');
   close(input);
   close(output)
end;

begin
  init;
  erfen
end.