求助 dij+二分 WA#4#13

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<ext/pb_ds/priority_queue.hpp> 
using namespace std;
using namespace __gnu_pbds;
int n,m,b;
int f[10010],co[10010];
int l,r;
int ans=0x7f7f7f7f;
struct edge
{
    int node;
    int w;
    edge(int node_,int w_):
        node(node_),w(w_){}
};
vector<edge> v[50010];
long long dis[50010];
int vis[50010];
inline bool dijkstra(int x)
{
    __gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag> q;
    memset(dis,127,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[1]=0;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        pair<int,int> k=q.top();
        q.pop();
        if(vis[k.second]) continue;
        vis[k.second]=1;
        dis[k.second]=k.first;
        for(vector<edge>::iterator i=v[k.second].begin();i!=v[k.second].end();i++)
        {
            if(co[i->node]>x) continue;
            q.push(make_pair(i->w+k.first,i->node));
        }
    }
    if(dis[n]<=b) return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
        co[i]=f[i];
    }
    sort(f+1,f+1+n);
    for(int i=1;i<=m;i++)
    {
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        if(x!=y)
        {
            v[x].push_back(edge(y,w));
            v[y].push_back(edge(x,w));
        }
    }
    if(!dijkstra(f[n]))
    {
        printf("AFK\n");
        return 0;
    }
    l=1;
    r=n;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(dijkstra(f[mid]))
        {
            ans=min(ans,f[mid]);
            r=mid-1;
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}