看来这题数据的确略水

一开始咱想的是从起点和终点分别两边spfa取出到个点的最短路与路上经过的最大值，然后枚举各点看起点到此点再由此点到终点是否小于限制b，若可行就取一下两段路经过的最大点，依次枚举算出最小。但后来想想显然是不对的，如果有一条路到中间某一点前一段既不是最短路后一段也不是，但长度依然小于b，且经过最大点最小，那这个算法就卡掉了。但依然得了90分，看来数据的确略水了。

最后附上代码好了，算是个教训？大家似乎有些也想过非二分的做法吧233

#include<cstdio>
#include<cctype>
#include<queue>
#include<algorithm>
#define loop(i,j,k) for(int i=j;i<=k;++i)
#define leaf(u) for(int i=head[u];i;i=next[i])
#define smax(a,b) a>b?a:b
#define smin(a,b) a<b?a:b
typedef long long ll;
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c-'-'))f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(ll x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int maxn=10001;
const int maxm=50001;
const int inf=0x7effffff;
int n,m,b,u,v,w,a[maxn],ans=inf;
int head[maxm*2],to[maxm*2],val[maxm*2],next[maxm*2],cnt;
inline void add_edge(int u,int v,int w){
    to[++cnt]=v,val[cnt]=w,next[cnt]=head[u],head[u]=cnt;
}
ll d1[maxn],md1[maxn];
bool inq[maxn];
queue<int> q;
inline void spfa1(){
    fill(d1+1,d1+n+1,inf);
    d1[1]=0;md1[1]=a[1];q.push(1);inq[1]=1;
    while(!q.empty()){
        int u=q.front();q.pop();inq[u]=0;
        leaf(u){
            int v=to[i];
            if(d1[u]+val[i]<d1[v]){
                d1[v]=d1[u]+val[i];md1[v]=smax(md1[u],a[v]);
                if(!inq[v]) q.push(v),inq[v]=1;
            }
        }
    }
}
ll d2[maxn],md2[maxn];
inline void spfa2(){
    fill(d2+1,d2+n+1,inf);
    d2[n]=0;md2[n]=a[n];q.push(n);inq[n]=1;
    while(!q.empty()){
        int u=q.front();q.pop();inq[u]=0;
        leaf(u){
            int v=to[i];
            if(d2[u]+val[i]<d2[v]){
                d2[v]=d2[u]+val[i];md2[v]=smax(md2[u],a[v]);
                if(!inq[v]) q.push(v),inq[v]=1;
            }
        }
    }
}
inline int koto(){
    in(n);in(m);in(b);
    loop(i,1,n) in(a[i]);
    loop(i,1,m) in(u),in(v),in(w),add_edge(u,v,w),add_edge(v,u,w);
    spfa1();
    spfa2();
    int fl=0;
    loop(i,1,n){
        if((d1[i]-inf)&&(d2[i]-inf)&&(d1[i]+d2[i]<b)){
            fl=1;ll tmp=smax(md1[i],md2[i]);
            ans=smin(ans,tmp);
        }
    }
    if(fl) out(ans);else putchar('A'),putchar('F'),putchar('K');
}
int zero=koto();
int main(){;}