90pts 求调Wa#8

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=1e5+5,N=1e4+5,inf=2147483647;
struct edge{
	int start,end,c;
}e[M];
int n,m,b;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int dis[N],vis[N];
int cost[N];
int head[M],cnt=0;
inline void add(int u,int v,int c){
	e[++cnt].end=v;
	e[cnt].start=head[u];
	head[u]=cnt;
	e[cnt].c=c;
}

int dijkstra(int money){
	for(int i=1;i<=n;i++){
		dis[i]=1e9;vis[i]=0;
	}
	dis[1]=0;
	if(money<cost[1]) return 0;
	q.push(make_pair(dis[1],1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].start){
			int v=e[i].end;
			if(cost[v]>money) continue;
//			if(vis[v]) continue;
			if(dis[v]>dis[u]+e[v].c&&vis[v]==0){
				dis[v]=dis[u]+e[v].c;
				q.push(make_pair(dis[v],v));
			}
		}
	}
//	cout<<dis[n];
	if(dis[n]<=b){		
		return 1;
	}else{
		return 0;
	}
	 
}


signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("","r")
	int u,v,c;
	int l=0,r=0;
	cin>>n>>m>>b;
	for(int i=1;i<=n;i++){
		cin>>cost[i];
		r=max(r,cost[i]);
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>c;
		add(u,v,c);
		add(v,u,c);
	}
	r=1000000005;
	if(dijkstra(r)==0){
		cout<<"AFK";
		return 0;
	}	
	while(l<r){
		int mid=(l+r)/2;
		if(dijkstra(mid)==0){
			l=mid+1;
		}else{
			r=mid;
		}	
	}
	cout<<l;
	
	return 0;
}