记录编号	453792	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.165 s
提交时间	2017-09-25 09:11:31	内存使用	0.63 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define ll long long 
using namespace std;
/*
	二分答案；
	r=最大交费城市费用；
	然后跑spfa
	如果某个到达点val比二分的guess大 
	就不跑这个边；
	然后最后求出起点到终点最大距离。
	如果最大距离比油箱大，那就是跑不到，
	否则可以跑到说明这个guess合法； 
	spfa复杂度为o(nm)
	最坏情况下，m=n^2;即o(n^3);
	堆优化dijkstra复杂度稳定为o(mlogn)
	最坏为o(n^2logn);
	启示，以后最短路都用dijkstra; 
*/
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<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=10010;
vector <int> g[maxn],w[maxn];
int n,m,st,en,s;
int val[maxn];
int l,r;
/*int d[maxn];
bool induilie[maxn];
queue<int>duilie;
inline bool spfa(int guess){
	if(val[st]>guess||val[en]>guess)return false; 
	memset(d,127,sizeof(d));
	d[st]=0;
	duilie.push(st);
	induilie[st]=1;
	while(duilie.size()){
		int u=duilie.front();duilie.pop();
		for(int i=0;i<g[u].size();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];
				if(!induilie[v]){
					induilie[v]=1;
					duilie.push(v);
				}
			}
		}
		induilie[u]=0;
	}
	if(d[en]>s)return false;
	else return true;
}*/
struct dd{
	int v,id;
	inline bool operator <(const dd & a)const {
		return v>a.v;
	}
};
bool done[maxn];
int d[maxn];
inline bool dij(int guess){
	if(val[st]>guess||val[en]>guess)return false;
	memset(done,0,sizeof(done));
	memset(d,127,sizeof(d));
	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;
		for(int i=0;i<g[u].size();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 false;
	else return true;
}
inline void erfen(){
	//cout<<l<<" "<<" "<<r<<endl;
	while(l+1<r){
		int m=(l+r)>>1;
		//cout<<l<<" "<<m<<" "<<r<<endl;
		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");return 0;}
	else erfen();
	return 0;
}