RT,拜谢

#include<bits/stdc++.h>
using namespace std;
struct node
{
int to;
int len;
int next;
}
e[100005];

int head[100005],num;
long long dis[100005];
int n,m,b;
long long f[100005];

void add(int from,int to,int dis)
{
	e[++num].to=to;
	e[num].len=dis;
	e[num].next=head[from];
	head[from]=num;
}

const int INF=1e9;
priority_queue < pair< long long , int > > q; 
bool vis[100005];

long long dijkstra(int mid)
{
    // if(f[1]>mid)return 1;
	for(int i=1;i<=n;i++)dis[i]=INF;
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		int t=q.top().second;q.pop();
		if(vis[t])
		{
			continue;
		}
		vis[t]=1;
		for(int j=head[t] ; j ; j=e[j].next)
		{
			if(dis[e[j].to]>dis[t]+e[j].len and f[e[j].to]<=mid)
			{
				dis[e[j].to] = dis[t]+e[j].len;
				q.push(make_pair(-dis[e[j].to],e[j].to));
			}
		}
	}
	return dis[n];
}

bool check(int mid)
{
	if(dijkstra(mid)<=b)
	{
		return 1;
	}
	else return 0;
}

int ac(int l,int r)
{
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	return l;
}

int main()
{
	cin>>n>>m>>b;
	long long maxx=-1;
	for(int i=1;i<=n;i++)cin>>f[i],maxx=max(maxx,f[i]);
	for(int i=1;i<=m;i++)
	{
		int u,v,l;cin>>u>>v>>l;
		add(u,v,l);add(v,u,l);
	}
	if(!check(maxx))
	{
	cout<<"AFK";
	return 0;
	}
	cout<<ac(1,maxx);
	return 0;
}