rt，没看题解之前觉得不需要最短路，二分答案check的时候直接从1号点开始dfs一遍，途中把不合要求的都剪枝，最终看第n号点是否访问到即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct edge{
	int to,c;
};
vector<edge> u[11451];
int n,m,b,f[11451],l,r,mid;//方便起见把mid定为dfs时的费用限制
bool vis[11451];
void dfs(int x,int hp){
	if(hp<0||f[x]>mid) return;
	vis[x]=1;
	for(int i=0;i<u[x].size();++i){
		int t=u[x][i].to,v=u[x][i].c;
		if(!vis[t]&&f[t]<=mid) dfs(t,hp-v);
	}
}
signed main(){
	cin>>n>>m>>b;
	for(int i=1;i<=n;++i){
		cin>>f[i];r=max(r,f[i]);
	} 
	for(int i=1;i<=m;++i){
		int x,y,z;
		cin>>x>>y>>z;
		edge p;p.to=y;p.c=z;
		u[x].push_back(p);
		p.to=x;
		u[y].push_back(p);
	}
	mid=0x7f7f7f7f;
	dfs(1,b);
	if(!vis[n]){
		cout<<"AFK";
		return 0;
	}
	while(l+1<r){
		memset(vis,0,sizeof(vis));
		mid=(l+r)/2;
		dfs(1,b);
		if(vis[n]) r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}