20pts求条

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Edge{
    int to,dis,next;
}edge[50004];int n,m,b;
int head[60004],vis[50004],d[50004],a[50004];
int cnt; 
void addedge(int from,int to,int dis) {
    edge[++cnt].next = head[from]; 
    edge[cnt].dis = dis;
    edge[cnt].to = to;
    head[from] = cnt;
}
queue<int>q;
bool spfa(int need) {
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    vis[1] = 1;
    q.push(1);
    while(!q.empty()) {
        int cur = q.front();
        q.pop(); vis[cur] = 0;
        for(int i = head[cur];i;i = edge[i].next) {
            int toto = edge[i].to;
            if(d[toto] > d[cur] + edge[i].dis) {
                if(a[toto] > need) continue;
                d[toto] = d[cur] + edge[i].dis;
                if(vis[toto] == 0) {
                    vis[toto] = 1;
                    q.push(toto);
                }
            }
        }
    }
    if(d[n] < b) {
        return true;
    }
    return false;
}
signed main() {

    cin >> n >> m >> b;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for(int i = 1;i <= m;i++) {
        int u,v,w;
        cin >> u >> v >> w;
        addedge(u,v,w);
        addedge(v,u,w);
    }
    if(!spfa(1000000000)){
        cout << "AFK" << endl;
        return 0;
    }
    int l = 1,r = 1e9 + 10;
    while(l < r) {
        int mid = (l + r) / 2;
        if(spfa(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << l;
}

ACon#4#7#11 剩下全部RE