WA on#8

求dalao调代码qwq:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
const int N=50005;
const int inf=INT_MAX;

int n,m,k;
int u,v,w;
int l=inf,r,ans=inf;
int f[N],vis[N];
vector<pii>G[N];
struct node{int x,p,h;};

bool dijsktra(int maxx){
    memset(vis,0,sizeof vis);
    queue<node>q;q.push({1,f[1],k});
    while(!q.empty()){
        node cur=q.front();q.pop();
        if(vis[cur.x])continue;
        vis[cur.x]=1;
        for(int i=0;i<G[cur.x].size();i++){
            int y=G[cur.x][i].first;
            int w=G[cur.x][i].second;
            if(max(cur.p,f[y])<=maxx&&cur.h-w>=0){
                if(y==n)
                    return 1;
                q.push({y,max(cur.p,f[y]),cur.h-w});
            }
        }   
    }

    return 0;
}

int main(){
    cin>>n>>m>>k;

    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++){
        cin>>u>>v>>w;
        G[u].push_back(make_pair(v,w));
        G[v].push_back(make_pair(u,w));
    }

    while(l<=r){
        int mid=l+r>>1;
        if(dijsktra(mid))
            r=mid-1,ans=mid;
        else 
            l=mid+1;
    }

    if(ans==inf)puts("AFK");
    else cout<<ans<<endl;
    return 0;
}