Miku

一个小小二分+spfa

二分经过的最贵的点，然后跑spfa判断行不行。

没啥思维难度

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> 
#define int long long
using namespace std;
int n,m;
int b;
int f[100001];
struct b{
    int f,t,v;
    int ne;
}ed[5000001];
int vis[100001];
int l,r;
queue <int> q;
int p;
int head[100001];
int dis[100001];
void add(int f,int t,int v){
    p++;
    ed[p].f=f;
    ed[p].t=t;
    ed[p].v=v;
    ed[p].ne=head[f];
    head[f]=p;
    return ;
}
int x,y,z;
int check(int x){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=ed[i].ne){
            int v=ed[i].t;
            if(f[v]>x)
            continue;
            if(dis[v]>dis[u]+ed[i].v){
                dis[v]=dis[u]+ed[i].v;
                if(!vis[v])
                q.push(v);
            }
        }
    }
    return dis[n]<=b ? 1 : 0;
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&b);
    for(int i=1;i<=n;++i){
        scanf("%lld",&f[i]);
    }
    for(int i=1;i<=m;++i){
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    int l=1;r=1000001001;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(check(mid))
        r=mid-1;
        else
        l=mid+1;    
    }
    if(l==1000001002)
    cout<<"AFK";
    else
    cout<<l<<endl;

    return 0;
}