就是普普通通的dijkstra+二分啊

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 5e4 + 10;typedef pair<int, int> pii;
struct edge{
	int to, nxt, val;
}ed[M << 1];
priority_queue<pii> q;
int cnt, head[M], n, m, f[M], b, dis[M], vis[M];
void add(int u, int v, int w) {
	ed[++cnt].to = v;
	ed[cnt].val = w;
	ed[cnt].nxt = head[u];
	head[u] = cnt;
}
bool ck(int x) {
	if(x < f[1]) return 0;
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	while(!q.empty()) q.pop();
	dis[1] = 0;
	q.push(make_pair(0, 1));
	while(!q.empty()) {
		int u = q.top().second; q.pop();
		if(vis[u]) continue;
		++vis[u];
		for(int i = head[u]; i; i = ed[i].nxt) {
			if(f[ed[i].to] <= x && dis[ed[i].to] > dis[u] + ed[i].val) {
				dis[ed[i].to] = dis[u] + ed[i].val;
				q.push(make_pair(dis[ed[i].to], ed[i].to));
			}
		} 
	}
	if(dis[n] <= b)return 1;
	return 0;
}
signed main() {
//	freopen("P1462_3.in", "r", stdin);
	int r = 0;
	scanf("%d%d%d", &n, &m, &b);
	for(int i = 1; i <= n; ++i) scanf("%d", &f[i]), r += f[i];
	for(int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w); add(v, u, w);
	}
	int l = 0;
	while(l < r) {
		int mid = (long long)l + r >> 1;
		if(ck(mid)) r = mid;
		else l = mid + 1;
	}
	if(!ck(l)){cout << "AFK"; return 0;}
	cout << l << endl;
	return 0;
}