求助 91分 WA#4

用的dijkstra+二分，蒟蒻实在想不到哪里丢分了

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const int N = 10010, M = 50010;
int head[N], s[N], f[N], tot, vis[N];
ll dis[N];
int n, m, b;

struct Node {
    int v, edge, next;
}arr[M << 1];

struct City {
    int x;
    ll dis;
    City(int X, int DIS) : x(X), dis(DIS) {}
    bool operator > (const City& o) const { return dis > o.dis; }
};
priority_queue< City, vector<City>, greater<City> > q;

void insert(int a, int b, int c) {
    arr[++tot].v = b;
    arr[tot].edge = c;
    arr[tot].next = head[a];
    head[a] = tot;
}

void dij(int md) {
    memset(dis, 0x3f3f3f3f3f3f3f3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    if (f[1] > md) { return; }
    dis[1] = 0;
    q.push(City(1, 0));
    while (!q.empty()) {
        City cur = q.top(); q.pop();
        vis[cur.x] = 1;
        for (int i = head[cur.x]; i != 0; i = arr[i].next) {
            if (dis[arr[i].v] > cur.dis + arr[i].edge && f[arr[i].v] <= md && !vis[arr[i].v]) {
                dis[arr[i].v] = cur.dis + arr[i].edge;
                q.push(City(arr[i].v, dis[arr[i].v]));
            }
        }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> b;
    for (int i = 1; i <= n; ++i) {
        cin >> f[i];
        s[i] = f[i];
    }
    sort(s + 1, s + n + 1);

    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        insert(a, b, c);
        insert(b, a, c);
    }

    dij(s[n]);
    if (dis[n] > b) {
        cout << "AFK";
        return 0;
    }

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        dij(s[mid]);
        if (dis[n] > b) { l = mid + 1; }
        else { r = mid; }
    }
    cout << s[l];
    return 0;
}