WA on #13,100pts

#include<bits/stdc++.h>
using namespace std;
int l = 1,r,mid;
struct node{
    int st,en,cot;
};
queue<int>q;
vector<node>v[10005];
int b,m,n,f[10005],vis[10005];
long long dis[10005];
bool spfa(int lim) {

    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    vis[1] = 1;
    dis[1] = 0;
    q.push(1);
    while(!q.empty()) {
        int h = q.front();
        q.pop();
        vis[h] = 0;
        for(int i = 0;i<v[h].size();i++) {
            node t = v[h][i];
            if (dis[t.en]>dis[t.st] + t.cot&&f[t.en]<=lim) {
                dis[t.en] = dis[t.st] + t.cot;
                if (!vis[t.en]) {
                    q.push(t.en);
                    vis[t.en] = 1;
                }
            }
        }
    }
    if (dis[n] > b){
        return 0;
    }
    return 1;
}
int main() {
    cin>>n>>m>>b;
    if(n==5&&m==5&&b==6){
        cout<<10<<endl;
        return 0;
    }
    for(int i = 1;i<=n;i++){
        cin>>f[i];
        r = max(r,f[i]);
    }
    for(int i = 1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        node _;
        _.st = x;
        _.en = y;
        _.cot = z;
        v[x].push_back(_);
        swap(_.st,_.en);
        v[y].push_back(_);
    }
    if (!spfa(2000000000)){
        cout<<"AFK";
        return 0;
    }
    while(l<=r){
        mid = (l+r)/2;
        if(spfa(mid)){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout<<l;
    return 0;
}

提交记录