Wa 了第 8 个点，下载下来是直接输出AFK

蒟蒻用的是 Dij ，麻烦大佬帮忙看看错。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
int n,m,b;
const int N = 1e4+5 , M = 2e5+5;
int h[N],ver[M],Next[M],edge[M],cnt;
int pd,p[N],dist[N],vst[N];
void Add(int x,int y,int z) {
	Next[++cnt]=h[x];
	ver[cnt]=y;
	edge[cnt]=z;
	h[x]=cnt;
}
void Dij() {
	queue<pair<int,int> >q;
	q.push(make_pair(0,1));
	for(int i=1;i<=n;i++)
	dist[i]=0x7fffffff;
	memset(vst,0,sizeof(vst));
	dist[1]=0;
	while(q.size()) {
		int u=q.front().second;
		q.pop();
		if(vst[u])continue;
		vst[u]=1;
		for(int i=h[u],v; i; i=Next[i]) {
			if(dist[v=ver[i]]>dist[u]+edge[i])
				if(p[v]<=pd) {
					dist[v]=dist[u]+edge[i];
					q.push(make_pair(-dist[v],v));
				}
		}
	}
}
bool check(int x) {
	pd=x;
	if(x<p[1]||x<p[n])return false;
	Dij();
	if(dist[n]>=b)return false;
	return true;
}
signed main() {
	scanf("%lld%lld%lld",&n,&m,&b);
	int maxx=0;
	for(int i=1; i<=n; i++){
		scanf("%lld",&p[i]);
		maxx=max(maxx,p[i]);
	}
	for(int i=1; i<=m; i++) {
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		if(x==y) continue;
		Add(x,y,z);
		Add(y,x,z);
	}
	if(!check(maxx)) {
		puts("AFK");
		return 0;
	}
	int l=1,r=maxx;
	while(l<r) {
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%lld",r);
	return 0;
}