gyy20081201 @ 2023-02-20 15:42:20
#include<bits/stdc++.h>
#define N 30005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
struct node{
int to,nxt,w;
}E[4*N];
int n,m,b,f[N],l,r=0;
int head[N],cnt;
ll dis[N];
bool vis[N];
queue<int> q;
void add(int x,int y,int z){
E[++cnt].to=y;
E[cnt].w=z;
E[cnt].nxt=head[x];
head[x]=cnt;
}
bool spfa(int sb){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
q.push(1);
vis[1]=1;
dis[1]=0;
while(!q.empty()){
int p=q.front();
q.pop();
vis[p]=0;
for(int i=head[p];i;i=E[i].nxt){
int v=E[i].to;
if(dis[p]+E[i].w<dis[v]&&!vis[v]&&f[v]<=sb){
dis[v]=dis[p]+E[i].w;
q.push(v);
vis[v]=1;
}
}
}
if(dis[n]<b) return true;
return false;
}
int main(){
scanf("%d%d%d",&n,&m,&b);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
r=max(f[i],r);
}
l=max(f[1],f[n]);
for(int i=1,a,s,c;i<=m;i++){
scanf("%d%d%d",&a,&s,&c);
if(a==s) continue;
add(a,s,c);
add(s,a,c);
}
if(!spfa(inf)){
printf("AFK");
return 0;
}
while(l<=r){
int mid=(l+r)>>1;
if(spfa(mid)) r=mid-1;
else l=mid+1;
}
printf("%d",l);
}