RE求助

rt

#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef pair<int, int> PII;

const int N = 1e4 + 4, M = 5e4 + 5, INF = 0x3f3f3f3f3f3f3f3f;
int dist[N];
bool vis[N], ok[N];
struct node
{
    int to, w;
};
vector<node> a[N];
int fee[N], n, m, life;
priority_queue<PII, vector<PII>, greater<PII>> q; 

bool check(int maxf)
{
    for (int i = 1; i <= n; i ++)
    {
        if(fee[i] > maxf) ok[i] = false;
        else ok[i] = true;
    }
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    q.push({0, 1});
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.second, dis = t.first;
        if (vis[ver] || !ok[ver]) continue;
        vis[ver] = 1;

        for (int i = 0; i < a[ver].size(); i ++)
        {
            node j = a[ver][i];
            if (!ok[j.to]) continue;
            if (dist[j.to] > dis + j.w)
            {
                dist[j.to] = dis + j.w;
                q.push({dist[j.to], j.w});
            }
        }
    }
    if (dist[n] == INF) return false;
    return dist[n] <= life;
}

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &life);
    int maxf = 0;
    for (int i = 1; i <= n; i ++)
    {
        scanf("%lld", &fee[i]);
        maxf = max(maxf, fee[i]);
    }
    for (int i = 1; i <= m; i ++)
    {
        int x, y, z;
        scanf("%lld %lld %lld", &x, &y, &z);
        a[x].push_back({y, z});
        a[y].push_back({x, z});
    }

    if (!check(maxf))
    {
        cout << "AFK";
        return 0;
    }
    int l = 1, r = maxf, ans = maxf;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = r;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}