首先有两个最短路，可以考虑把一个东西拿出来二分，也就是可以二分最小值，但是注意不要用SPFA他死了，可以用Dij跑最短路，再二分，效率会大大提高

1.SPFA

#include
using namespace std;
const int N=1e4+;
const int M=1e5+;
int n,m,tot,head[M];
long long f[N],d[N],b,a[N];
bool vis[N];
struct node{int to,next;long long val;}e[M];
void add(int u,int v,int w){e[++tot].to=v;e[tot].next=head[u];e[tot].val=w;head[u]=tot;}
bool spfa(long long k){
queue q;
if(a[]>k||a[n]>k)return false;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)d[i]=LLONG_MAX; d[]=;q.push();vis[]=; while(!q.empty()){ int u=q.front();q.pop();vis[u]=; for(int i=head[u];i;i=e[i].next){ int v=e[i].to,z=e[i].val; if(a[v]>k)continue;
if(d[v]>d[u]+z){
d[v]=d[u]+z;
if(!vis[v])q.push(v),vis[v]=;
}
}
}
return d[n]<=b; } int main(){ //freopen("a.in","r",stdin); long long c; scanf("%d%d%lld",&n,&m,&b); for(int i=;i<=n;i++) scanf("%lld",&f[i]),a[i]=f[i]; for(int i=,u,v;i<=m;i++){ scanf("%d%d%lld",&u,&v,&c); add(u,v,c);add(v,u,c); } sort(f+,f+n+); int l=,r=n,best=-; while(l>;
if(spfa(f[mid]))
best=mid,r=mid-;
else
l=mid+;
}
if(spfa(f[l]))best=l;
if(best<)puts("AFK");
else printf("%lld\n",f[best]);
}

2.DIJ

#include
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
using namespace std;
const int N=1e4+;
const int M=1e5+;
int n,m,tot,head[M],st,ed;
int f[N],d[N],b,a[N];
bool vis[N];
struct node{int to,next,val;}e[M];
priority_queue > q;
void add(int u,int v,int w){e[++tot].to=v;e[tot].next=head[u];e[tot].val=w;head[u]=tot;}
bool spfa(int k){
if(a[st]>k||a[ed]>k)return false;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)d[i]=INT_MAX; d[st]=;q.push(make_pair(,st));; while(!q.empty()){ int u=q.top().second;q.pop(); if(vis[u])continue; vis[u]=; for(int i=head[u];i;i=e[i].next){ int v=e[i].to,z=e[i].val; if(a[v]>k)continue;
if(d[v]>d[u]+z){
d[v]=d[u]+z;
q.push(make_pair(-d[v],v));
}
}
}
return d[ed]<=b; } int main(){ scanf("%d%d%d%d%d",&n,&m,&st,&ed,&b); for(int i=;i<=n;i++) scanf("%d",&f[i]),a[i]=f[i]; for(int i=,u,v,c;i<=m;i++){ scanf("%d%d%d",&u,&v,&c); add(u,v,c);add(v,u,c); } sort(f+,f+n+); int l=,r=n,best=-; while(l>;
if(spfa(f[mid]))
best=mid,r=mid-;
else
l=mid+;
}
if(spfa(f[l]))best=l;
if(best<)puts("-1");
else printf("%d\n",f[best]);
}