求助dij+二分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <vector>
using namespace std;

const int N = 1e5+10;
typedef pair<int,int> PII;
typedef long long ll;
int h[N],w[N],e[N],ne[N],idx;
ll d[N],f[N];
bool st[N];
int n,m,b;

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}

bool check(ll k)
{
    if(f[1] > k || f[n] > k) return false;
    for(int i = 0;i <= n;i++)
    {
        d[i] = INT_MAX;
        st[i] = false;
    }
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    d[1] = 0;
    heap.push({0,1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second,blood = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver];i != -1;i = ne[i])
        {
            int j = e[i];
            if(d[j] > blood + w[i] && f[j] <= k)
            {
                d[j] = blood + w[i];
                if(!st[j]) heap.push({d[j],j});
            }
        }
    }
    return (d[n] <= b);
}

int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m >> b;
    long long l = 1e9 + 10,r = -1;
    for(int i = 1;i <= n;i++) 
    {
        scanf("%lld",&f[i]);
        r = max(r,f[i]);
    }
    l = max(f[1],f[n]);
    for(int i = 0;i < m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        if(a==b) continue;
        add(a,b,w),add(b,a,w);
    }
    while(l < r)
    {
        long long mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(!check(l)) puts("AFK");
    else cout << l  << endl;
}