题目求：交费最多的一次的最小值。符合二分求最大值最小
二分答案的特点:具有单调性。
此题的单调性是金钱越多,则可以走的路也越多。因此符合二分答案的要求
特别注意:1.hp可以是0 
         2.道路要建双向边，因此M要多开一倍，不然会re
正确性验证：因为hp固定，假设钱无限多，那么可以走的道路是固定的
那么可走的道路与金钱的数量成反比，二分到最后的就是能走到奥格瑞玛的最小金钱。
code:
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
const int N = 1e4 + 10, M = 1e5 + 20, maxf = 1e9;
typedef pair<int, int>pii;
int h[N], idx;
bool st[N];
ll dist[N];
struct edge{
    ll to, from, w;
    ll ne;
}E[M];
int n, m, hp, f[N];

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

bool check(int mid)
{
    // cout << mid << endl;
    priority_queue<pii, vector<pii>, greater<pii>>heap;
    heap.push({0, 1});
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0;
//  cout << f[1];
    if(f[1] > mid)return false;

    while(heap.size())
    {
        auto t = heap.top();
        int no = t.y;
        heap.pop();

        if(st[no])continue;
        st[no] = true;

        for(int i = h[no];~i; i = E[i].ne)
        {
            int j = E[i].to;
            if(f[j] > mid)continue;
            if(dist[j] > dist[no] + E[i].w && dist[no] + E[i].w <= hp)
            {
                dist[j] = dist[no] + E[i].w;
                heap.push({dist[j], j});
            }
        }
    }
    // cout << dist[n] << endl;
    if(dist[n] != 0x3f3f3f3f3f3f3f3f)return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> hp;
    memset(h, -1, sizeof h);

    for(int i = 1;i <= n;i++)cin >> f[i];
    for(int i = 1;i <= m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

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