Subtask #1死了

#include<bits/stdc++.h>
using namespace std;
const long long INF = 9e18,N = 1e4 + 10;
int n,m,b;
long long int dist[N],f[N];
struct to{
	int p;
	long long damage;
	bool operator < (const to& rhs)const
	{
		return damage > rhs.damage;
	}
};
vector<to> road[N];
char went[N];
priority_queue<to> q;
bool dij(int ub)
{
	int start,health = b;
	for(int i = 0;i <= n;i++)
	{
		dist[i] = INF;
	}
	dist[1] = 0;
	q.push((to){1,0});
	memset(went,0,sizeof(went));
	while(!q.empty())
	{
		to x = q.top();
		q.pop();
		start = x.p;
		if(went[start] == 1 || f[start] > ub)
		{
			continue;
		}
		went[start] = 1;
		for(int j = 0;j < road[start].size();j++)
		{
			int end = road[start][j].p;
			if(dist[end] > dist[start] + road[start][j].damage && f[end] <= ub)
			{
				dist[end] = dist[start] + road[start][j].damage;
				q.push((to){end,dist[end]});
			}
		}
	}
	return dist[n] < b;
}
int merge(int l,int r)
{
	while(l < r)
	{
		int mid = (l + r) / 2;
		if (dij(mid))
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	return r;
}
int main()
{
	cin >> n >> m >> b;
	for(int i = 1;i <= n;i++)
	{
		cin >> f[i];
	}
	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		road[u].push_back({v,w});
		road[v].push_back({u,w});
	}
	int ans = merge(1,1e9);
	if(ans != 1e9)
	{
		cout << ans;
	}
	else
	{
		cout << "AFK";
	}
	return 0;
}