求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,b,f[10005],ans=LLONG_MAX;
struct node{
    int v,xue;
    bool operator<(node ac)const{
        return xue>ac.xue;
    } 
}now,tmp;
int dis[10005];
struct road{
    int x,y,c;
}x[50005];
bool vis[10005];
vector<node>e[10005];
bool cmp(road q,road p){
    return q.c<p.c;
}
void dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=f[1];
    now.v=1;
    now.xue=b;
    priority_queue<node> q;
    q.push(now);
    while(!q.empty()){
        now=q.top();
        q.pop();
        if (vis[now.v]==1){
            continue;
        }
        vis[now.v]=1;
        for(int i=0;i<e[now.v].size();i++){
            tmp=e[now.v][i];
            if (max(dis[now.v],f[tmp.v])<dis[tmp.v]&&now.xue-tmp.xue>=0){
                dis[tmp.v]=max(dis[now.v],f[tmp.v]);
                q.push({tmp.v,now.xue-tmp.xue});
            }
        }
    }
}
bool check(int h){
    for(int i=1;i<=n;i++){
        e[i].clear();
    }
    for(int i=1;i<=h;i++){
        e[x[i].x].push_back({x[i].y,x[i].c});
        e[x[i].y].push_back({x[i].x,x[i].c});
    }
    dijkstra();
    if (dis[n]!=0x3f3f3f3f){
        ans=min(ans,dis[n]);
        return true;//能走通 
    }else{
        return false;//不能走同 
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    for(int i=1;i<=m;i++){
        cin>>x[i].x>>x[i].y>>x[i].c;
    }
    sort(x+1,x+1+m,cmp);
    int l=1,r=m,res=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if (check(mid)){
            res=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    if (ans==LLONG_MAX){
        cout<<"AFK";
    }else{
        cout<<ans;
    }
    return 0;
}