rt,

Subtask #1 AC，Subtask #0 WA #6 #8 #10

思路很简单，从起点开始跑 BFS，到终点结束。

队列记录当前节点，权值和，最多一次收取的费用。

到终点时更新最多一次收取的费用。

代码：

#include <stdio.h>
#include <vector>
#include <queue>

#define MAXN 16384
#define int long long

using std::vector;
using std::queue;

struct EDGE{int u,v,l;};
struct P{int v,l,maxn;};
vector<EDGE> g[MAXN];
queue<P>	 q;
bool vis[MAXN],flag;
int n,m,b,f[MAXN],STEP = 2147483647;

void BFS(int s,int t){
	q.push((P){s,0,f[s]});
	while(!q.empty()){
		P wx = q.front();
		auto &v = wx.v;
		q.pop();
		for(int i = 0;i < g[v].size();i ++){
			if(g[v][i].v == t && wx.l+g[v][i].l <= b){
				flag = true;
				STEP = std::min(STEP,std::max(wx.maxn,g[v][i].u));
				break ;
			}
			if(!vis[g[v][i].v]){
				vis[g[v][i].v] = true;
				q.push((P){g[v][i].v,wx.l+g[v][i].l,std::max(g[v][i].u,wx.maxn)});
			}
		}
	}
}

signed main(){
	scanf("%lld%lld%lld",&n,&m,&b);
	for(int i = 1;i <= n;i ++) scanf("%lld",&f[i]);
	while(m --){
		int u,v,l;
		scanf("%lld%lld%lld",&u,&v,&l);
		g[u].push_back((EDGE){f[v],v,l});
		g[v].push_back((EDGE){f[u],u,l});
	}
	BFS(1,n);
	if(!flag) puts("AFK");
	else	printf("%lld\n",STEP);

	return 0;
}