求调

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int id;
    long long v;
};
int n,m,k;
long long f[10005];
vector<Edge> ve[10005];
long long ans=-1;
long long maxmoney=0;
queue<int> q;
long long dis[10005];
bool vis[10005];
bool check(int x){
    if(f[1]>x) return false;
    for(int i=1;i<=n;i++){
        vis[i]=0;
        dis[i]=1e18;
    }
    dis[1]=0;
    vis[1]=1;
    q.push(1);
    while(!q.empty()){
        int p=q.front();
        q.pop();
        if(vis[p]) continue;
        vis[p]=1;
        for(int i=0;i<ve[p].size();i++){
            int id=ve[p][i].id,v=ve[p][i].v;
            if(f[id]>x) continue;
            if(dis[p]+v<dis[id]){
                dis[id]=dis[p]+v;
                q.push(id);
            }
            if(id==n){
                if(dis[n]>=k) return false;
                else return true;
            }
        }
    }
    return false;
}
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>f[i];
        maxmoney=max(f[i],maxmoney);
    }
    for(int i=1;i<=m;i++){
        Edge A,B;
        int x,y,z;
        cin>>x>>y>>z;
        A.id=y;
        A.id=z;
        B.id=x;
        B.id=z;
        ve[x].push_back(A);
        ve[y].push_back(B); 
    }
    long long l=1,r=maxmoney;
    while(l<=r){
        long long mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    if(ans==-1) printf("AFK\n");
    else printf("%lld",ans);
    return 0;
}