萌新求助27分1462

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
const int maxm=50010;
const long long inf=10000000000010;
int n,m;
long long cost[maxn];
long long cosss[maxn];
long long blood;
struct EDGE{
    int next,to;
    long long w;
}edge[maxm<<1];
int head[maxn],ant=0;
void add(int q,int z,long long qz)
{
    edge[ant].to=z;
    edge[ant].w=qz;
    edge[ant].next=head[q];
    head[q]=ant++;
}
bool spfa(long long maxx)
{
    long long dis[maxn];
    int can[maxn];
    for(int i=1;i<=n;i++)
    {
    dis[i]=inf; 
    if(maxx<cost[i])can[i]=1;
    }
    if(can[1]==1)return 0;
    int vis[maxn];
    queue<int> que;
    que.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!que.empty())
    {
        int q=que.front();
        que.pop();
        vis[q]=0;
        for(int i=head[q];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(can[v]==1)continue;
            if(dis[v]>dis[q]+edge[i].w)
            {
                dis[v]=dis[q]+edge[i].w;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    if(dis[n]>blood)return 0;
    else return 1;
}
int main(){
    memset(head,-1,sizeof(head));
    scanf("%d%d%lld",&n,&m,&blood);
    for(int i=1;i<=n;i++)
    {
        long long co;
        scanf("%lld",&co);
        cost[i]=co;
        cosss[i]=co;
    }
    sort(cosss+1,cosss+1+n);
    for(int i=1;i<=m;i++)
    {
        int q,z;
        long long qz;
        scanf("%d%d%lld",&q,&z,&qz);
        add(q,z,qz);
        add(z,q,qz);
    }
    if(!spfa(cosss[n])){
        cout<<"AFK"<<endl;
        return 0;
    }
    int l=1,r=n;
    while(l!=r)
    {
        int mid=(r+l)/2;
        if(spfa(cosss[mid]))r=mid;
        else l=mid+1;
    }
    cout<<cosss[l]<<endl;
    return 0;
}