记录编号	518747	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	真的菜	是否通过	通过
代码语言	C++	运行时间	0.128 s
提交时间	2018-10-30 21:41:25	内存使用	0.63 MiB

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=10010;
int n,m,st,en,s;
vector<int>g[maxn],w[maxn];
int val[maxn];

struct dd{
	int val,id;
	inline bool operator <(const dd & a)const {
		return val>a.val;
	}
};

int d[maxn];
bool done[maxn];
inline bool dij(int guess){
	if(val[st]>guess||val[en]>guess)return false;
	memset(d,127,sizeof(d));
	memset(done,0,sizeof(done));
	d[st]=0;
	priority_queue< dd > duilie;
	duilie.push((dd){0,st});
	while(duilie.size()){
		dd tou=duilie.top();
		duilie.pop();
		int u=tou.id;
		if(done[u])continue;
		done[u]=true;
		int len=g[u].size();
		for(int i=0;i<len;i++){
			int v=g[u][i];
			if(val[v]>guess)continue;
			if(d[v]>d[u]+w[u][i]){
				d[v]=d[u]+w[u][i];
				duilie.push((dd){d[v],v});
			}
		}
	}
	if(d[en]<=s)return true;
	return false;
}
int l,r;
inline void erfen(){
	while(l+1<r){
		m=(l+r)>>1;
		if(dij(m))r=m;
		else l=m;
	}
	if(dij(l))printf("%d\n",l);
	else printf("%d\n",r);
}
int main(){
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	n=read();m=read();st=read();en=read();s=read();
	for(int i=1;i<=n;i++)val[i]=read(),r=max(r,val[i]);
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),ww=read();
		g[u].push_back(v);
		g[v].push_back(u);
		w[u].push_back(ww);
		w[v].push_back(ww);
	}
	if(!dij(r))puts("-1");
	else erfen();
	return 0;
}