我直接小根堆优化的dij+二分（找钱的方案），用的第二篇题解的思路

昨天调到今天力，有点崩溃了

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 100005, M = 100005;
ll f[N], dis[N], n, m, b;
bool vis[N];
int head[N], ver[M], edge[M], nxt[M], num = 0; //Chain Forward Star

void add(int x, int y, int c) {
	ver[++num] = y, edge[num] = c;
	nxt[num] = head[x], head[x] = num;
}

priority_queue < pair<ll, int> > q;

bool chk(ll cst) {
	for(int i = 1; i <= n; i++) {
		dis[i] = LONG_LONG_MAX;
		vis[i] = 0;	
	}
	
	q.push(make_pair(0, 1));
	dis[1] = 0;
	if(f[1] > cst) return false;
	while(!q.empty()) {
		pair <ll, int> p = q.top();
		q.pop();
		ll dist = -p.first, x = p.second;
		
		if(x == n) {
			if(dis[n] > b) return false;
			return true;
		}
		if(vis[x]) continue;
		vis[x] = true;
		for(int i = head[x]; i > 0; i = nxt[i]) {
			ll y = ver[i], c = edge[i];
			if(dist + c <= dis[y] && f[y] <= cst)  {
				dis[y] = dist + c;
//				cout  << y << "》》"<< dis[y] << endl;
				q.push(make_pair(-dis[y], y));
			}
		}
	}
//	for(int i = 1; i <= n; i++)
//		cout << dis[i] << " ";
//	cout << endl;
//	if(dis[n] < cst) return true;
//	return false;
}

int main() {
//	freopen("a.aaa" , "w", stdout);
	cin >> n >> m >> b;
	for(int i = 1; i <= n; i++) cin >> f[i];
	
	int x, y, c;
	for(int i = 1; i <= m; i++) {
		cin >> x >> y >> c;
		add(x, y, c);
		add(y, x, c);
	}
	
	long long l = 1, r = 1000000005;
	if(!chk(r)) {
		cout << "AFK" << endl;
		return 0;
	}
	long long mid = (l + r) >> 1;
	while(l <= r) {
		bool tmp = chk(mid);
//		cout << l << " " << r << " " << tmp<< endl;
		if(tmp == 1) {
//			cout  << " Hello " << r << endl;
			r = mid - 1;
			mid = (l + r) >> 1;
		} else {
			l = mid + 1;
			mid = (l + r) >> 1;
		}
	} 
	cout << l << endl; 
	return 0;
}