本文共 1418 字，大约阅读时间需要 4 分钟。

题目

思路

如果我们二分答案，显然就转化为了部分点不能去的dij板子，但是，二分也有技巧，由于题目的询问问的是最大值，所以我们可以二分点，换言之，就是二分的是下标，但check用的是下标里的值。

#include
   
    #include
    
     #include
     
      using namespace std;int b[10101],e=1,first[10101];struct f{    int to; int w; int net;} a[110001];bool book[10101];struct f2{    int x,y;} p;bool operator <(const f2 &x,const f2 &y){    return x.x>y.x;}priority_queue
      
        c;void jto(int x,int y,int z){    a[e].to=y; a[e].w=z; a[e].net=first[x]; first[x]=e; e++;}int n,m,q=1,bb;int yuy[10101],yu[10101],v[10101];bool check(int ybt){    if (yu[q]>ybt||yu[n]>ybt) return 0; for (int i=1;i<=n;i++) {     b[i]=1000000010;  book[i]=0;  if (yu[i]>ybt) book[i]=1; } b[q]=0; p.x=0,p.y=q; c.push(p); while (c.size()) {     int u=c.top().y;  c.pop();  if (book[u]) continue;  book[u]=1;  for (int i=first[u];i;i=a[i].net)  {      if (b[a[i].to]>b[u]+a[i].w)   {       b[a[i].to]=a[i].w+b[u];    p.x=b[a[i].to];    p.y=a[i].to;    c.push(p);   }  } }    if (b[n]<=bb)    {           return 1;    } else {           return 0;    } }int main(){    cin>>n>>m>>bb; int x,y,z,l=1,r=n,ans; for (int i=1;i<=n;i++) cin>>yu[i],yuy[i]=yu[i]; for (int i=1;i<=m;i++) {     cin>>x>>y>>z;  if (x==y) continue;  jto(x,y,z);  jto(y,x,z); } sort(yuy+1,yuy+1+n); if (!check(yuy[n])) {     cout<<"AFK";  return 0; } ans=yuy[n]; while (l<=r) {     int mid=(l+r)>>1;  if (check(yuy[mid])) r=mid-1,ans=yuy[mid];  else l=mid+1; } cout<