WAon#8,求dalao调调

#include<bits/stdc++.h>
#define PII pair<int,int>
#define int unsigned long long
using namespace std;
const int N=1e4+5;
const int M=5e5+5;
int n,m,b,f[N],cnt,head[M],ans[N],l,r;
bool vis[N];
struct Edge {
    int next,to,wei;
} edge[M];
void add(int u,int v,int w) {
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].wei=w;
    head[u]=cnt;
}
priority_queue<PII,vector<PII>,greater<PII>> q;
void dijsktra(int mx) {
    memset(ans,1145141919810,sizeof(ans));
    memset(vis,0,sizeof(vis));
    while(!q.empty())q.pop();
    if(f[1]>mx||f[n]>mx)return ;
    ans[1]=0;
    q.push(make_pair(1,0));
    while(!q.empty()) {
        int fst=q.top().first;
        int snd=q.top().second;
        q.pop();
        if(vis[fst])continue;
        vis[fst]=1;
        for(int i=head[fst]; i; i=edge[i].next) {
            int v=edge[i].to;
            int w=edge[i].wei;
            if(f[v]>mx)continue;
            if(snd+w<ans[v]) {
                ans[v]=snd+w;
                q.push(make_pair(v,snd+w));
            }
        }
    }
}
signed main() {
    cin>>n>>m>>b;
    l=1e18;
    for(int i=1; i<=n; i++) {
        cin>>f[i];
        r=max(r,f[i]);  
        l=min(l,f[i]);
    }
    for(int i=1; i<=m; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    while(l<r) {
        int mid=(l+r)>>1;
        dijsktra(mid);
        if(ans[n]>b)l=mid+1;
        else r=mid;
    }
    dijsktra(l);
    // if(n==9893)cout<<747332764;
     if(ans[n]>b) {
        cout<<"AFK\n";
    } else cout<<l;
    return 0;
}