这边很多题解都被#12的数据hack掉了

code:

/*
    hack:
        3 2 2
        1
        2
        1
        1 2 1
        2 3 1
    ans:
        2
    output:
        AFK
*/
#include <bits/stdc++.h>
#define int long long
#define N 100005
#define INF 1000000005
using namespace std;
typedef pair<int, int> PII;
int n, m, b, x, y, z, dis[N], f[N];
bool vis[N];
struct Edge
{
    int from, to, len;
    Edge(int from, int to, int len) : from(from), to(to), len(len) {}
};
vector<Edge> edges[N];
bool spfa(int x)
{
    if (x < f[1])
        return false;
    memset(dis, 127, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push(PII(0, 1));
    dis[1] = 0;
    while (!q.empty())
    {
        PII u = q.top();
        q.pop();
        int to = u.second;
        int to_dis = u.first;
        if (vis[to])
            continue;
        vis[to] = true;
        for (auto y : edges[to])
        {
            if (f[y.to] > x)
                continue;
            int len = to_dis + y.len;
            if (vis[y.to])
                continue;
            if (f[y.to] <= x && dis[y.to] > len)
            {
                dis[y.to] = len;
                q.push(PII(dis[y.to], y.to));
            }
            // if (dis[y.to] > len)
            // {
            //     dis[y.to] = len;
            //     if (!vis[y.to] && f[y.to] <= x)
            //     {
            //         vis[y.to] = true;
            //         q.push(PII(dis[y.to], y.to));
            //     }
            // }
            // if (f[y.to] <= x && dis[y.to] > len)
            // {
            // }
        }
        // vis[to] = false;
    }
    if (dis[n] < b)
        return true;
    return false;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &b);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &f[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%lld%lld%lld", &x, &y, &z);
        // if (x == y)
        //     continue;
        edges[x].push_back(Edge(x, y, z));
        edges[y].push_back(Edge(y, x, z));
    }
    if (!spfa(INF))
    {
        // puts("AFK");
        printf("AFK");
        return 0;
    }
    int l = 1, r = INF, mid;
    bool flag;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        flag = spfa(mid);
        if (flag)
            r = mid - 1;
        else
            l = mid + 1;
        // cout << l << endl;
    }
    printf("%lld", l);
    return 0;
}