题目中的表述很明显是一道二分答案+最短路的题目，二分收取的费用x判断能否到达奥格瑞玛。检验函数用SPFA跑最短路，注意，费用高于x的点不能使用。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int MAXN=10005,MAXM=50005,INF=0x7fffffff/2;
int read(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return fh*rv;
}
int n,m,b,fee[MAXN],nume,head[MAXN];
struct egde{
int to,nxt,kil;
}e[MAXM*2];
void adde(int from,int to,int kil){
e[++nume].to=to;
e[nume].nxt=head[from];
e[nume].kil=kil;
head[from]=nume;
}
bool chk(int x){
int dis[MAXN];
bool f[MAXN]={0};
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
dis[i]=INF;
}
dis[1]=0;
f[1]=1;
queue <int>spfa;
spfa.push(1);
while(!spfa.empty()){
int u=spfa.front();
spfa.pop();
f[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(fee[v]<=x&&dis[v]>dis[u]+e[i].kil){
dis[v]=dis[u]+e[i].kil;
if(!f[v]){
spfa.push(v);
f[v]=1;
}
}
}
}
if(dis[n]<=b) return 1;
else return 0;
}
int main(){
freopen("in.txt","r",stdin);
n=read();m=read();b=read();
int l=0,r=0,mid=0;
for(int i=1;i<=n;i++){
fee[i]=read();
r=max(r,fee[i]);
}
l=max(fee[1],fee[n]);
for(int i=1;i<=m;i++){
int u=read(),v=read(),kil=read();
adde(u,v,kil);
adde(v,u,kil);
}
if(!chk(r)){
cout<<"AFK"<<endl;
return 0;
}
while(l<=r){
mid=(l+r)>>1;
if(chk(mid)){
r=mid-1;
}else l=mid+1;
}
cout<<l;
fclose(stdin);
return 0;
}