记录编号	22104	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.557 s
提交时间	2010-11-17 08:37:10	内存使用	1.58 MiB

{城市 NOIP模拟2010-11-16
 二分答案 最短路径
 Author: yangbohua
 Time: 2010-11-17}
 
program cost;
type
  bian=record
    v,w,next:longint;
  end;
  heaptype=record
    v:longint;
    d:int64;
  end;

var
  list,hpos,c,d:array[0..10001] of longint;
  map:array[0..100001] of bian;
  heap:array[0..10001] of heaptype;
  b:array[0..10001] of boolean;
  n,m,s,t,hl,i,r1,r2,r3,mid,l,r,midcost,i1,p,j:longint;
  vv:int64;

procedure swap(x,y:longint);
begin
  heap[0]:=heap[x];
  heap[x]:=heap[y];
  heap[y]:=heap[0];
  hpos[heap[x].v]:=x;
  hpos[heap[y].v]:=y;
end;

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


begin
  assign(input,'cost.in');
  reset(input);
  assign(output,'cost.out');
  rewrite(output);

  readln(n,m,s,t,vv);
  for i:=1 to n do
  begin
    readln(c[i]);
    d[i]:=c[i];
  end;
  for i:=1 to m do
  begin
    readln(r1,r2,r3);
    map[i*2-1].v:=r2;
    map[i*2-1].w:=r3;
    map[i*2-1].next:=list[r1];
    list[r1]:=i*2-1;
    map[i*2].v:=r1;
    map[i*2].w:=r3;
    map[i*2].next:=list[r2];
    list[r2]:=i*2;
  end;
  sort(1,n);
  l:=1;
  r:=n+1;
  d[n+1]:=maxlongint;
  while l<r do
  begin
    mid:=(l+r) div 2;
    midcost:=d[mid];
    if (midcost<c[s]) or (midcost<c[t]) then
    begin
      l:=mid+1;
      continue;
    end;
    fillchar(b,sizeof(b),false);
    fillchar(hpos,sizeof(hpos),0);
    fillchar(heap,sizeof(heap),0);
    for i:=1 to n do
    begin
      heap[i].v:=i;
      heap[i].d:=maxlongint;
      hpos[i]:=i;
      if c[i]<=midcost then
      begin
        b[i]:=true;
      end;
    end;
    hl:=n;
    heap[s].d:=0;
    swap(1,s);
    while hl>0 do
    begin
      i:=heap[1].v;
      swap(1,hl);
      hl:=hl-1;
      i1:=2;
      while i1<=hl do
      begin
        if (i1<hl) and (heap[i1+1].d<heap[i1].d)
          then inc(i1);
        if heap[i1].d<heap[i1 div 2].d then
        begin
          swap(i1,i1 div 2);
          i1:=i1*2;
        end
        else break
      end;
      p:=list[i];
      while p>0 do
      begin
        j:=map[p].v;
        if hpos[j]<=hl then
          if (b[j]) and (heap[hpos[i]].d+map[p].w<heap[hpos[j]].d) then
          begin
            heap[hpos[j]].d:=heap[hpos[i]].d+map[p].w;
            j:=hpos[j];
            while (j>1) and (heap[j].d<heap[j div 2].d) do
            begin
              swap(j,j div 2);
              j:=j div 2;
            end;
          end;
        p:=map[p].next;
      end;
    end;
    if heap[hpos[t]].d<=vv
      then r:=mid
      else l:=mid+1;
  end;
  if d[r]<maxlongint
    then writeln(d[r])
    else writeln(-1);
  close(input);
  close(output);
end.