【2017.8.6普及模拟】最大（max）
题目：
走进丛林的BT开始了他在丛林的探险，一天晚上，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.
比赛的时候打了个递归
理所当然的40分
听DALAO讲解后恍然大悟
我们二分出答案
用答案来标记所有点是否可用
if weight[i]<=mid then bz[i]:=true（可用）
else bz[i]:=false;（不可用）
从起点到终点做一遍SPFA
然后
if dis[终点]<=早餐营养值 then r:=mid-1
else l:=mid+1;
标程：（请勿抄袭，后果很严重）
var n,m,s,t,i,j,k,x:longint; ans,ka,l,r,mid:int64; weight:array[1..10000]of int64; d:array[0..50000]of int64; a:array[0..50000,1..2]of longint; st,en:array[0..10000]of longint; bz,bj:array[1..10000]of boolean; data:array[0..5000000]of longint; dis:array[0..10000]of int64; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=a[(l+r)div 2,1]; repeat while a[i,1]<mid do inc(i); while a[j,1]>mid do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin assign(input,'max.in'); assign(output,'max.out'); reset(input); rewrite(output); readln(n,m,s,t,ka); for i:=1 to n do readln(weight[i]); for i:=1 to m do begin readln(a[i*2-1,1],a[i*2-1,2],d[i*2-1]); a[i*2,1]:=a[i*2-1,2]; a[i*2,2]:=a[i*2-1,1]; d[i*2]:=d[i*2-1]; end; qsort(1,m*2); st[a[1,1]]:=1; en[a[1,1]]:=1; for i:=2 to m*2 do if a[i,1]=a[i-1,1] then inc(en[a[i,1]]) else begin st[a[i,1]]:=i; en[a[i,1]]:=i; end;//边集存储 l:=1; r:=maxlongint; while l<=r do //二分 begin mid:=(l+r)div 2; if mid=3900 then writeln; fillchar(bz,sizeof(bz),1); for i:=1 to n do if weight[i]>mid then bz[i]:=false;//标记可用点 fillchar(bj,sizeof(bj),1); bj[s]:=false; data[1]:=s; i:=0; j:=1; fillchar(dis,sizeof(dis),$7f); dis[s]:=0; if bz[s] then while i<j do begin inc(i); if st[data[i]]<>0 then for k:=st[data[i]] to en[data[i]] do if(dis[a[k,2]]>dis[data[i]]+d[k])and(bz[a[k,2]])then begin dis[a[k,2]]:=dis[data[i]]+d[k]; if bj[a[k,2]] then begin inc(j); data[j]:=a[k,2]; bj[a[k,2]]:=false; end; end; bj[data[i]]:=true; end;//SPFA if dis[t]<=ka then r:=mid-1 else l:=mid+1; end; writeln(l); close(input); close(output); end.
