输出 r 100pts.
by Haber @ 2022-08-04 18:22:58
@[luoyx](/user/520056) 因为此时 mid 是答案，但是你又把 l+1所以答案有问题。
by Haber @ 2022-08-04 18:23:46
@[haber](/user/345900) 我写这么长时间的二分模板错了？
这个是[P1462](https://www.luogu.com.cn/problem/P1462)
的AC代码。只看二分。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b;
int f[10005];
int u,v,w;
int head[10005],ecnt;
int maxb;
bool flg;
struct edge{
int v,w,nxt;
}e[100005];
int dis[10005];
void add(int u,int v,int w){
e[ecnt].v=v;
e[ecnt].nxt=head[u];
e[ecnt].w=w;
head[u]=ecnt;
ecnt++;
}
void spfa(int mid){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
queue<int> q;
q.push(1);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i+1;i=e[i].nxt){
int v=e[i].v;
if(f[v]>mid) continue;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push(v);
}
}
}
if(dis[n]>b) flg=false;
else flg=true;
}
signed main(){
cin>>n>>m>>b;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++){
cin>>f[i];
maxb=max(maxb,f[i]);
}
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
int l=f[1],r=maxb,mid;
while(l<=r){
mid=(l+r)/2;
spfa(mid);
if(flg){
r=mid-1;
}
else{
l=mid+1;
}
}
spfa(maxb);
if(!flg) cout<<"AFK";
else cout<<l;
return 0;
}
```
by luoyx @ 2022-08-04 18:31:30
@[luoyx](/user/520056) 不知道，~~我二分的边界和最后答案一直都乱搞~~，wssb
by Haber @ 2022-08-04 18:42:43
我以前写二分老喜欢 T 掉，直到教练给了这个板子(((
by RP_INT_MAX @ 2022-08-04 18:49:59
@[luoyx](/user/520056) 二分板子
```cpp
int l=/*左边界*/,r=/*右边界*/;
while(l<=r) {
int mid=l+r>>1;
if(check(mid)) l=mid+1;//r=mid-1;，视情况而定
else r=mid-1;//l=mid+1;，视情况而定
}
//最后ans=l
```
by RP_INT_MAX @ 2022-08-04 18:51:02
@[2021WuYueYang](/user/566289) 位运算没加括号（doge
by luoyx @ 2022-08-04 19:39:15
@[luoyx](/user/520056) 可以不加的，加号的优先级比右移大
by RP_INT_MAX @ 2022-08-05 12:44:19