二分+最短路
首先题目询问路线中收费最大的最小值 考虑二分答案

在这里存在两个限制因素血量和路费。 每个点都存在一个路费但并没有路费限制，而血量的话我们要求到达重点是血量大于等于0
我们考虑二分路径费用最大值考虑二分性质 最大值越大可通过的点就越多血量花费的可能就越大。因此当二分时血量小于等于满足条件，我们将右边界调小。同理当血量大于满足条件说我们需要走一些其他的点降低血量消耗考虑将答案调大

将l=f[1]是为了过最后一个hack点。

# include <bits/stdc++.h>
using namespace std;
#define int long long 
int n,m,b;
const int N=1e4+10,M=1e5*2+10;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],w[M],idx;
int d[N];
int f[N];
bool st[N];
bool check(int x)
{
    memset(d,0x3f,sizeof(d));
    memset(st,false,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,1});
    while(q.size())
    {
    auto t=q.top();
    int t1=t.first,t2=t.second;
    q.pop();
    if(st[t2])
    continue;
    st[t2]=1;
    for(int i=h[t2];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(d[j]>t1+w[i]&&f[j]<=x)
        {
        d[j]=t1+w[i];
        q.push({d[j],j});     
        }
        }
    }
    if(d[n]<=b)
    return true ;
    return false ;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
signed main()
{   
    int l,r;
    memset(h, -1, sizeof h);
    cin>>n>>m>>b;
    for(int i=1;i<=n;i++)
    cin>>f[i];
    while(m--)
    {
    int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c);
    add(b,a,c); 
    }
    if(!check(1000000001))
    {
    cout<<"AFK";
    return 0;
    }
    l=f[1],r=1e9;
    while(l<r)
    {
    int mid=l+r>>1;
    if(check(mid))r=mid;
    else l=mid+1;
    }
    cout<<l<<endl;
}