第八个点莫名WA

如题,程序如下

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define N 10010

int n,m,s,f[N],d[N];
int _min[N],ans;
bool vis[N];
int head[N],tot;
struct lll{int nxt,from,to,l;}c[100010];
priority_queue<int,vector<int>,greater<int> >q;

void add(int u,int v,int l){
    c[tot].from=u;
    c[++tot].to=v;
    c[tot].l=l;
    c[tot].nxt=head[u];
    head[u]=tot;
}

bool Dij(int exp){
    if(exp<f[1]||exp<f[n]) return 0;
    for(int i=1;i<=n;i++) {
        _min[i]=1000000010;
        if(f[i]>exp) vis[i]=1;
        else vis[i]=0;
    }
    _min[1]=0;q.push(1);
    while(!q.empty()) {
        int now=q.top();
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        for(reg int i=head[now];i;i=c[i].nxt)
            if(_min[c[i].to]>_min[now]+c[i].l) {
                _min[c[i].to]=_min[now]+c[i].l;
                q.push(c[i].to);
            }
    }
    if(_min[n]<=s) return 1;
    return 0;
}

int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(reg int i=1;i<=n;i++) {
        scanf("%d",&f[i]);
        d[i]=f[i];
    }
    for(reg int i=1;i<=m;i++) {
        int ai,bi,ci;
        scanf("%d%d%d",&ai,&bi,&ci);
        if(ai==bi) continue;
        add(ai,bi,ci);
        add(bi,ai,ci);
    }
    sort(d+1,d+n+1);
    int l=1,r=n,mid;
    if(!Dij(d[n])) {
        printf("AFK\n");
        return 0;
    }
    ans=d[n];r=n;
    while(l<=r) {
        mid=(l+r)/2;//>>1
        if(Dij(d[mid])) {
            ans=d[mid];
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}