80分求调

WA on #7 #8 #11

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define int long long
using namespace std;
const int N = 10010;
struct Graph{
    int v , w;
};vector<Graph> g[N];
struct node{
    int ver;
    int distance;
    bool operator < (const node &_) const {
        return _.distance < distance;
    } 
};
int n , m , x , ans = -1;
int f[N];
int dist[N];
int vis[N];
bool dijkstra(int x){
    if(f[1] > x) return false;
    for(int i = 1;i <= n;i++) dist[i] = 1e18;
    memset(vis , 0 , sizeof vis);
    priority_queue<node> q;
    q.push({1 , 0});
    dist[1] = 0LL;
    while(!q.empty()){
        node t = q.top(); q.pop();
        int ver = t.ver , distance = t.distance;
        if(vis[ver]) continue; vis[ver] = 1;
        for(auto it : g[ver]){
            int j = it.v , w = it.w;
            if(f[j] <= x && dist[j] > distance + w){
                dist[j] = distance + w;
                q.push({j , dist[j]});
            }
        }
    }
    return dist[n] <= x;
}
int l = 1 , r = 1000000001;
signed main(){
    cin >> n >> m >> x;
    for(int i = 1;i <= n;i++) cin >> f[i];
    while(m--){
        int u , v , w;
        scanf("%lld%lld%lld" , &u , &v , &w);
        g[u].push_back({v , w});
        g[v].push_back({u , w});
    }
    while(l <= r){   
        int mid = l + r >> 1;
        if(dijkstra(mid)) r = mid - 1 , ans = mid;
        else l = mid + 1; 
    }
    if(ans == -1) puts("AFK");
    else printf("%lld" , ans);
    return 0;
}