90pts求条玄关

WA on #4 (应输出AFK）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
const int inf = 0x7f7f7f7f;
int n, m, b, cnt, maxk;
int head[maxn], dis[maxn], a[maxn];
bool vis[maxn];
struct edge {
    int to, next, val;
} e[maxn];
void add(int u, int v, int w){
    e[++cnt].next = head[u], e[cnt].to = v, e[cnt].val = w, head[u] = cnt;
}

struct node{
    int dis, pos;
    bool operator < (const node &x) const{
        return x.dis < dis;
    }
};

priority_queue<node> q;

bool Dijkstra(int x){
    if (a[1] > x) return false;
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    dis[1] = 0;
    q.push((node){0, 1});
    while (!q.empty()){
        node tmp = q.top();
        q.pop();
        int u = tmp.pos, d = tmp.dis;
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].next){
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].val && a[v] <= x){
                dis[v] = dis[u] + e[i].val;
                if(!vis[v]) {
                    q.push((node){dis[v], v});
                }
            }
        }
    }
    if (dis[n] > b) return false;
    return true;
} 
int main(){
    cin >> n >> m >> b;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        maxk = max(maxk, a[i]);
    }
    for (int i = 1, u, v, w; i <= m; i++){
        cin >> u >> v >> w;
        add (u, v, w); add (v, u, w);
    }
    if (!Dijkstra(inf)){
        cout << "AFK";
        return 0;
    }
    int l = 1, r = maxk, mid = (l + r) >> 1;
    while (l < r){
        memset (vis, 0, sizeof vis);
        memset (dis, 0, sizeof dis);
        if (Dijkstra(mid)){
            r = mid;
        } else {
            l = mid + 1;
        }
        mid = (l + r) >> 1;
    }
    cout << l << endl;
    return 0;
}