WA on #13,100pts求条玄2关

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
struct node
{
    int to,nex,w;
}e[N*10];
int head[N*10],cnt,dis[N];
int f[N],n,m,b;
bool vis[N];
void add(int x,int y,int z)
{
    cnt++;
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].nex=head[x];
    head[x]=cnt;
}
priority_queue<pair<int,int> >q; 
int dij(int k)
{
    while (q.size()) q.pop();
    for (int i=1;i<=n;++i)
    {
        dis[i]=1e18/3;
        vis[i]=0;
    }
    q.push(make_pair(0,1));
    dis[1]=0;
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nex)
        {
            int y=e[i].to;
            if (f[y]>k) continue;
            if(dis[x]+e[i].w<dis[y])
            {
                dis[y]=dis[x]+e[i].w;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
    return (dis[n]>b);
}
signed main()
{
    cin >> n >> m >> b;
    int l=1e9,r=-1;
    for (int i=1;i<=n;++i)
    {
        cin >> f[i];
        l=min(l,f[i]);
        r=max(r,f[i]); 
    }
    for (int i=1;i<=m;++i)
    {
        int x,y,z;
        cin >> x >> y >> z;
        add(x,y,z);
        add(y,x,z);
    }
    while (l<r)
    {
        int mid=(l+r)/2;
        if (dij(mid)) 
        {   
            l=mid+1;
        } 
        else 
        {
            r=mid;
        }
    }
    if (dij(l))
    {
        puts("AFK");
    }
    else cout << l;
    return 0;
}
/*
5 5 6
10
5
2
10
0
1 2 4
2 5 2
2 4 1
3 5 2
5 5 1

10
*/