他发现，丛林的每棵树上都有些浆果，这些浆果都是他没见过的，所以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。
样例输入：
4 4 2 3 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3
样例输出：
10
其实这道题是一道破坏OJ平衡性的水题！
思路：二分（为什么在比赛时没想到呢？？？？）+SPFA（伟大的SPFA）。
先二分出一个答案，再用SPFA判断此答案符不符合条件，至于那个早餐能量，（完全扯淡！）直接一开始的时候把它 div 2就行了。
代码：
var n,m,i,j,k,x,y,z,s,ls,o,p,nl,l,r,mid:longint; f:array[0..10001,0..1001,1..2]of longint; a:array[0..10001]of longint; function pd(k:longint):boolean; var d,t:array[0..10001]of longint; i,j,x,y,z,s,l:longint; begin for i:=1 to 10000 do t[i]:=maxlongint; t[o]:=0; d[1]:=o; i:=0; j:=1; while i<j do begin inc(i); for l:=1 to f[d[i],0,1] do if a[f[d[i],l,1]]<=k then begin if t[f[d[i],l,1]]>t[d[i]]+f[d[i],l,2] then begin inc(j); d[j]:=f[d[i],l,1]; t[f[d[i],l,1]]:=t[d[i]]+f[d[i],l,2]; end; end; end; if (t[p]<>maxlongint)and(t[p]<=ls) then exit(true) else exit(false); end; begin assign(input,'max.in'); reset(input); assign(output,'max.out'); rewrite(output); readln(n,m,o,p,ls); ls:=ls div 2; for i:=1 to n do readln(a[i]); for i:=1 to m do begin readln(x,y,z); inc(f[x,0,1]); f[x,f[x,0,1],1]:=y; f[x,f[x,0,1],2]:=z; inc(f[y,0,1]); f[y,f[y,0,1],1]:=x; f[y,f[y,0,1],2]:=z; end; l:=a[o]; r:=maxlongint-l; while l<=r do begin mid:=(l+r) div 2; if pd(mid) then begin s:=mid; r:=mid-1; end else l:=mid+1; end; if s=0 then writeln(-1) else writeln(s); end.
