RT, 二分+堆优化 Dijkstra 求调

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e4 + 5, M = 2 * 5e4 + 5;
const int MAX = 1e9 + 5;
int n, m, b;
int f[N];
int h[N], e[M], ne[M], w[M], idx;
inline int read(){
    int s = 0; char ch = getchar();
    while(isdigit(ch)){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s;
}
inline void write(int x){
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void add(int a, int b, int c){
    ++idx;
    e[idx] = b, w[idx] = c;
     ne[idx] = h[a], h[a] = idx;
}
inline bool dijkstra(int max_cst){
    if(f[1] > max_cst)
        return false;
    priority_queue<pii, vector<pii>, greater<pii> > q;
    int dis[N]; bool st[N];
    memset(dis, 0x3f, sizeof dis), memset(st, false, sizeof st);
    dis[1] = 0, q.push((pii){dis[1], 1});
    while(!q.empty()){
        int now_id = q.top().second; q.pop();
        if(st[now_id])
            continue;
        st[now_id] = true;
        for(int i = h[now_id]; i != -1; i = ne[i]){
            int to_id = e[i], new_dis = dis[now_id] + w[i];
            if(dis[to_id] > new_dis && !st[to_id] && f[to_id] <= max_cst){
                dis[to_id] = new_dis;
                q.push((pii){dis[to_id], to_id});
            }
        }
    }
    return dis[n] < b;
}
int main(){
    n = read(), m = read(), b = read();
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
        f[i] = read();
    for(int i = 1; i <= m; i++){
        int a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    if(!dijkstra(MAX)){
        printf("AFK\n");
        return 0;
    }
    int l = 1, r = MAX;
    while(l <= r){
        int mid = l + r >> 1;
        if(dijkstra(mid))
            r = mid - 1;
        else
            l = mid + 1;
    }
    write(l);
    return 0;
}