题目大意： BT一天晚上发现丛林的每棵树上都有些浆果，BT想把这些果子都拿回去做研究，然而BT认为一次拿太多会很不爽，所以他想知道，他从营地到准备考察的地方，一每棵树上的浆果最大值的最小值。当然，BT的早餐能量有限，而从一棵树到另一棵树所需能量是已知的，BT要保证来回所需能量小于等于早餐所提供的能量。
输入：第一行5个正整数，n(1<=n<=10000)，m(1<=m<=25000)，s，t，st。分别表示有n棵树，m条路径，从营地s到考察处t，早餐的能量为st。 接下来有n行，每行1个正整数，fi。表示第i棵树上的浆果重量。 再接下来有m行，每行3个正整数，x，y，d (1<=x，y<=n)。表示第x棵树和第y棵树之间可通行，且所需能量为d。
输出： 一行，路径上浆果重量最大值的最小值。若BT无法从营地和考察地间走一个来回，则输出-1.
淼淼淼淼！
一道赤裸裸 的二分外加最短路！
二分枚举答案，删掉大于答案 的点即可。
再spfa，合法r左移，不合法l右移。
于是.....
184826 2167 2017王誉达 评测通过 100 65 ms 7.98 MB Pascal 2945 bytes 2017-08-06 16:02:41 注意细节！细节！细节！谨慎处理！
标程（请勿抄袭）：
var i:longint; j,k,m,n,o,p,l,s,t,r,mid,x,y,c,head,tail,q1:int64; b,f:array[1..100000,1..3] of int64; q,a,h,long:array[1..100000] of int64; bz,spfa:array[1..100001] of boolean; procedure insert(x,y,z:longint); begin inc(t); f[t,1]:=y; f[t,2]:=q[x]; f[t,3]:=z; q[x]:=t; end; function pd(a:longint):longint; begin if a=0 then exit(maxlongint) else exit(a); end; begin assign(input,'max.in');reset(input); assign(output,'max.out');rewrite(output); readln(n,m,x,y,c); c:=c div 2; for i:=1 to n do readln(a[i]); for i:=1 to m do begin readln(o,p,q1); insert(o,p,q1); insert(p,o,q1); end; l:=0;r:=9223372036854775806; mid:=(l+r) div 2; while l<=r do begin fillchar(bz,sizeof(bz),true); for i:=1 to n do begin if a[i]>mid then bz[i]:=false; long[i]:=0; end; if (bz[x]=false) or (bz[y]=false) then begin l:=mid+1; mid:=(l+r) div 2; //if mid*2<>l+r then mid:=mid+1; continue; end; fillchar(spfa,sizeof(spfa),true); head:=0;tail:=1;h[1]:=x;spfa[x]:=false; while head<tail do begin inc(head); k:=q[h[head]]; while k<>0 do begin if bz[f[k,1]]=false then begin k:=f[k,2]; continue; end; if long[h[head]]+f[k,3]<pd(long[f[k,1]]) then begin if spfa[f[k,1]] then begin inc(tail); h[tail]:=f[k,1]; spfa[f[k,1]]:=false; end; long[f[k,1]]:=long[h[head]]+f[k,3]; end; k:=f[k,2]; end; end; if (long[y]<>0) and (long[y]<=c) then begin r:=mid-1; mid:=(l+r) div 2; //if mid*2<>l+r then mid:=mid+1; end else begin l:=mid+1; mid:=(l+r) div 2; //if mid*2<>l+r then mid:=mid+1; end; end; ///writeln(long[y]); // if (long[y]=0) or (long[y]>c) then inc(mid); if mid*2<>l+r then inc(mid); writeln(mid); close(input);close(output); end.
