求助 80分

#include<bits/stdc++.h>
#define LO long long
using namespace std;
struct edge
{
    LO to,next,value;
}e[100010];
LO hd[10010],cnt;
LO q[10010],head,tail;
LO ext[10010];
LO dist[10010];//上面是spfa经典变量 
LO n,m,b;
LO cost[10010];//每个点花费 
LO help[10010];//维护点权 
LO ans;//结果 
LO lb,rb,mid;
void addedge(LO a,LO b,LO life)
{
    e[++cnt].to=b;
    e[cnt].next=hd[a];
    e[cnt].value=life;
    hd[a]=cnt;
}
int spfa(LO max_co)
{
    if(help[1]>max_co)return 0;//起点就让你花式爆炸 
    for(LO i(1);i<=n;++i)
    dist[i]=1000000005;
    memset(q,0,sizeof(q));
    head=0,tail=0;
    dist[1]=0;
    ext[1]=1;
    q[++tail]=1;
    while(head<tail)
    {
        head=(head+1)%10005;
        LO jb=q[head];
        ext[jb]=0;
        for(LO i=hd[jb];i;i=e[i].next)
        {
            LO gg=e[i].to;
            if(dist[gg]>dist[jb]+e[i].value&&help[gg]<=max_co)//花费过多的点去掉 
            {
                dist[gg]=dist[jb]+e[i].value;
                if(!ext[gg])
                {
                    tail=(tail+1)%10005;
                    ext[gg]=1;
                    q[tail]=gg;
                }
            } 
        }
    }
    if(dist[n]<=b)return 1;
    else return 0;
}
int main()
{
    cin>>n>>m>>b;
    for(LO i(1);i<=n;++i)
    {
        cin>>cost[i];
        help[i]=cost[i];
    }
    for(LO i(1);i<=m;++i)
    {
        LO x,y,z;
        cin>>x>>y>>z;
        addedge(x,y,z);
        addedge(y,x,z);
    }
    sort(cost+1,cost+n+1);
    lb=1,rb=n;
    if(!spfa(2000000005))
    {
        cout<<"AFK"<<endl;//再多的钱也救不活gg的术士 
        return 0;
    }
    while(lb<rb)//二分答案 
    {
        mid=(lb+rb)/2;
        if(spfa(cost[mid]))
        {
            rb=mid;
        } 
        else  //花费这么多也可以活就试试花费少一点 
        lb=mid+1;//不然加大投入
    }
    cout<<cost[lb]<<endl;
    return 0;
}