蒟蒻再次拜访

WA 36分？

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};
    while(isdigit(c)){x=x*10+c-'0';c=getchar();};
    return x*f;
}
typedef pair<int,int> pii;
priority_queue <pii,vector<pii>,greater<pii> > q;
const int maxn=10005,maxm=50005;
const int inf=0x3f3f3f3f;
struct edge{
    int v,w,next;
}e[maxm];
int cnt,head[maxn];
int n,m,b;
int f[maxn],ff[maxn];
int ans=-1;
int dis[maxn];
bool vis[maxn];
int maxx=-1;
void add(int u,int v,int w)
{
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
bool judge(int money) 
{
    if(money<f[1]||money<f[n])
    return 0;
    memset(dis,inf,sizeof(dis));
    for(int i=1;i<=n;i++)
    {
        if(f[i]>money)
        vis[i]=1;
        else vis[i]=0;
    }
    dis[1]=0;
    q.push(make_pair(dis[1],1));
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])
        {
            /*printf("%d yes\n",u);*/continue;
        }
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].v;
            if(!vis[v]&&dis[u]+e[i].w<dis[v])
            {

                dis[v]=dis[u]+e[i].w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
    //printf("shat %d %d\n",money,dis[n]);
    //printf("fff money=%d f[1]=%d vis[1]=%d f[n]=%d vis[n]=%d\n",money,f[1],vis[1],f[n],vis[n]);
    if(dis[n]<=b)
    return 1;
    else return 0;
}
void readdata()
{
    n=read(),m=read(),b=read();
    for(int i=1;i<=n;i++)
    {
        f[i]=read();
        ff[i]=f[i];
    }
    maxx=max(f[1],f[n]);
    sort(ff+1,ff+n+1);
    /*for(int i=1;i<=n;i++)
    printf("%d ",ff[i]);
    printf("hello\n");*/
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        a=read(),b=read(),c=read();
        add(a,b,c);
        add(b,a,c);
    }
    int l=1,r=n;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(ff[mid]>=maxx&&judge(ff[mid]))
        {   
            //printf("on no %d\n",ff[mid]);
            r=mid-1;
            ans=ff[mid];
        } 
        else l=mid+1;
    }
    if(ans!=-1)
    printf("%d",ans);
    else printf("AFK");
}
int main()
{
    //freopen("sss.in","r",stdin);
    readdata();
    return 0;
}