二分+SPFA 80pts 求条 （WA on #5#8）

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

int n, m, b, l = LLONG_MAX, r, f[10005], dis[10005], vis[10005];
struct node
{
    int v, w;
};
vector<node> g[10005];
queue<int> que;

bool spfa(int s, int lim, int b)
{
    for(int i = 1; i <= n; i++)
    {
        dis[i] = LLONG_MAX;
    }
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    vis[s] = 1;
    que.push(s);
    while(que.size())
    {
        int h = que.front();
        que.pop();
        vis[h] = 0;
        if(f[h] > lim)
        {
            continue;
        }
        for(int i = 0; i < g[h].size(); i++)
        {
            int v = g[h][i].v, w = g[h][i].w;
            if(f[v] > lim)
            {
                continue;
            }
            if(dis[v] > dis[h] + w)
            {
                dis[v] = dis[h] + w;
                if(!vis[v])
                {
                    que.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    if(dis[n] != dis[0])
    {
        if(dis[n] <= b)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}

signed main()
{
    cin >> n >> m >> b;
    for(int i = 1; i <= n; i++)
    {
        cin >> f[i];
        r = max(r, f[i]);
        l = min(l, f[i]);
    }
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[u].push_back({u, w});
    }
    if(!spfa(1, LLONG_MAX, b))
    {
        cout << "AFK";
        return 0;
    }

    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(spfa(1, mid, b))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l;

    return 0;
}