27分求助qwq

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF=0x3f3f3f3f;
int head[100010];
int nxt[100010];
int ver[100010];
ll edg[100010];
int tot=0;
ll vet[100010];//点权
int vis[100010];
int dis[100010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > emp;
int n,m,b;
inline void add(int x,int y,ll z)
{
    ver[++tot]=y;
    edg[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
}

bool check(int k)
{
    q=emp;
    if(k<vet[1]) return 0;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i];ll z=edg[i];
            {
                if(dis[y]>dis[x]+z&&vet[y]<=k)//大于最大点权的点不能放 
                {
                    dis[y]=dis[x]+z;
                    q.push(make_pair(dis[y],y));
                }
            }
        }
    }
    return dis[n]<=b;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>vet[i];
    }
    for(int i=1;i<=n;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    if(!check(INF))
    {
        cout<<"AFK\n";
        return 0;
    }
    sort(vet+1,vet+1+n);
    int l=0,r=n,mid;
    int ans=n;
    while(l<=r)
    {
        mid=(r-l)/2+l;
        bool k=check(vet[mid]);
        if(k)
        {
            r=mid-1;
            ans=vet[mid];
        }
        else
        {
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}