WA on #5#8#11-13

思路：二分+堆优化dijkstra。

判了 AFK，开了 long long，建了双向边，边数开了 2 倍，算上了第一个城市。

谢大佬！

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e4+4,M=1e5+5;
int n,m,HP;
int f[N],maxx;
int h[N],to[M],ne[M],idx,w[M];
int l,r,ans=-114514;
int dist[N];
bool vis[N];
void add(int a,int b,int ww){
    to[++idx]=b;
    w[idx]=ww;
    ne[idx]=h[a];
    h[a]=idx;
}
bool check(int x){
    memset(dist,0x3f,sizeof dist);
    memset(vis,false,sizeof vis);
    dist[1]=0;
    priority_queue<int,vector<int>,greater<int> > heap;
    heap.push(1);
    while(heap.size()){
        int t=heap.top();
        heap.pop();
        if(vis[t]) continue;
        vis[t]=true;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=to[i];
            if(f[j]<=x&&dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                heap.push(j);
            }
        }
    }
    return dist[n]<=HP;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof h);

    cin>>n>>m>>HP;
    for(int i=1;i<=n;i++) cin>>f[i],maxx=(maxx,f[i]);
    for(int i=1;i<=m;i++){
        int a,b,ww;
        cin>>a>>b>>ww;
        add(a,b,ww);
        add(b,a,ww);
    }

    l=max(f[1],f[n]),r=maxx;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans==-114514) cout<<"AFK"<<endl;
    else cout<<ans<<endl;
    return 0;
}