单源最短路，0pts，样例已过，hack能过2个点，蒟蒻求调

dijkstra

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf = 0x3f3f3f;
const int maxn = 10005;
const int maxm = 1e5 + 5;
int n, m, s, cnt = 0, ans, l = inf, r = -inf;
int val[maxn], dis[maxn], head[maxn];
struct Edge
{
    int nxt, to;
    ll dis;
}edge[maxm];
struct node
{
    int id;
    ll dis;
    bool operator < (const node & s)const
    {
        return s.dis < dis;
    }
};
priority_queue<node>q;

inline ll read()
{
    ll a = 0, f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        a = (a << 3) + (a << 1) + (c ^ '0');
        c = getchar();
    }
    return a * f;
}

inline void addedge(int u, int v, int w)
{
    cnt++;
    edge[cnt].nxt = head[u];
    edge[cnt].to = v;
    edge[cnt].dis = w;
    head[u] = cnt;
}

inline int dijkstra(int x)
{
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[1] = 0;
    q.push((node) { 1, 0 });
    while (!q.empty())
    {
        node temp = q.top();
        int u = temp.id;
        q.pop();
        if (dis[u] != temp.dis) continue;
        for (int i = head[u]; i; i = edge[i].nxt)
        {
            int v = edge[i].to;
            if (val[v] <= x && dis[u] + edge[i].dis < dis[v])
            {
                dis[v] = dis[u] + edge[i].dis;
                q.push((node) { v, dis[v] });
            }
        }
    }
    if (dis[n] <= s) return 1;
    return 0;
}

int main()
{
    n = read(), m = read(), s = read();
    for (int i = 1; i <= n; i++)
    {
        val[i] = read();
        l = min(l, val[i]);
        r = max(r, val[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        x = read(), y = read(), z = read();
        addedge(x, y, z);
        addedge(y, x, z);
    }
    if (!dijkstra(inf))
    {
        printf("AFK");
        return 0;
    }
    while (l <= r)
    {
        int m=l+r>>1;
        if (dijkstra(m))
        {
            ans = m;
            r = m - 1;
        }
        else l = m + 1;
    }
    printf("%d", ans);
    return 0;
}