求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,b,f[N],head[2*N],nxt[2*N],ver[2*N],w[2*N],tot;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int dis[N],vis[N];
void add(int x,int y,int z){
    ver[tot]=y;
    w[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot++;
}
bool dijkstra(int s){
    if(s<f[1]) return 0;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    while(!q.empty()) q.pop();
    q.push({0,1});
    while(q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]||f[u]>s) continue;
        vis[u]=1;
        for(int i=head[u];i;i=nxt[i]){
            int v=ver[i],wi=w[i];
            if(dis[u]+wi<dis[v]){
                dis[v]=dis[u]+wi;
                q.push({dis[v],v});
            }
        }
    }
    if(dis[n]<b) return 1;
    return 0;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    memset(head,0,sizeof(head));
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++) cin>>f[i];
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    if(dijkstra(1e9+5)==0){
        cout<<"AFK";
        return 0;
    }
    int L=0,R=1e9+5;
    while(L<R){
        int mid=L+R>>1;
        int ans=dijkstra(mid);
        if(ans) R=mid-1;
        else L=mid+1;
    }
    cout<<L;
    return 0;
}