【2017.8.6普及模拟】最大（max） (File IO): input:max.in output:max.out 时间限制: 1000 ms 空间限制: 262144 KB 具体限制 Goto ProblemSet
题目描述
走进丛林的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.
样例输入
4 4 2 3 8 8 5 6 10 2 1 2 2 4 1 1 3 4 3 4 3
样例输出
10
数据范围限制
数据：数据保证所有数（包括答案）在long long（pascal的 Int64）范围内（即小于2^63）
正解
二分+最短路。 就是二分找一个答案，用最短路看它是否合法，如果合法，在从更小的范围中去找他。否则从更大的范围去找，因为将范围扩大不会将原来已经扩展开的路关上，所以说，这题是可以用二分的。 那么正解就很容易得到了。
代码
var
n,m,s1,s2,ks,i,s,t,st,l,r,mid,p,long,u,ans,t1,t2:longint;
a,b,d,q,g:
array[
1..
20000]
of longint;
h:
array[
1..
10000,
1..
100,
1..
2]
of int64;
procedure qsort(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l;
j:=r;
mid:=a[(i+j)
div 2];
repeat
while (a[i]<mid)
do inc(i);
while (a[j]>mid)
do dec(j);
if i<=j
then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
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);
read(n,m,s1,s2,ks);
for i:=
1 to n
do
begin
read(a[i]);
end;
b:=a;
t1:=a[s1];
t2:=a[s2];
qsort(
1,n);
for i:=
1 to m
do
begin
read(s,t,st);
inc(g[s]);
h[s,g[s],
1]:=t;
h[s,g[s],
2]:=st;
inc(g[t]);
h[t,g[t],
1]:=s;
h[t,g[t],
2]:=st;
end;
for i:=
1 to n
do
begin
if (a[i]=t1)
or (a[i]=t2)
then
l:=i;
end;
r:=n;
while (l<=r)
do
begin
mid:=(l+r)
div 2;
for i:=
1 to n
do
q[i]:=i;
for i:=
1 to n
do
d[i]:=maxlongint;
d[s1]:=
0;
p:=s1;
long:=n;
while (p<=long)
do
begin
u:=q[p];
for i:=
1 to g[u]
do
begin
if (d[h[u,i,
1]]>d[u]+h[u,i,
2])
and (b[h[u,i,
1]]<=a[mid])
then
begin
d[h[u,i,
1]]:=d[u]+h[u,i,
2];
inc(long);
q[long]:=h[u,i,
1];
end;
end;
inc(p);
end;
if d[s2]<=ks
div 2 then
begin
r:=mid-
1;
end
else
begin
l:=mid+
1;
end;
end;
writeln(a[l]);
close(input);
close(output);
end.
