题目

#include<bits/stdc++.h>
using namespace std;
int n,m,hp;
struct Node{
	int to,val;
};
int w[10001];
vector<Node>a[10001];
long long js[10001];
bool check(int p,long long mid,long long val){
	if(p==n&&val<=hp){
		return 1;
	}
	if(val>js[p]||val>hp){
		return 0;
	}
	js[p]=val;
	bool bj=0;
	for(auto it:a[p]){
		if(check(it.to,mid,val+it.val)&&w[it.to]<=mid){
			bj=1;
		}
	}
	return bj;
}
int main(){
	scanf("%d%d%d",&n,&m,&hp);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<=m;i++){
		int u,v,val;
		scanf("%d%d%d",&u,&v,&val);
		a[u].push_back({v,val});
		a[v].push_back({u,val});
	}
	long long ans;
	bool bj=0;
	long long l=0,r=1e9;
	while(l<=r){
		long long mid=l+r>>1;
		for(int i=1;i<=n;i++){
			js[i]=1e10;
		}
		if(check(1,mid,0)){
			r=mid-1;
			ans=mid;
			bj=1;
		}
		else{
			l=mid+1;
			ans=mid+1;
		}
	}
	if(!bj){
		printf("AFK");
		return 0;
	}
	printf("%lld",ans);
	return 0;
}