记录编号	169380	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2015-07-08 17:42:41	内存使用	0.79 MiB

/*题目名称：城市
难度：高
考点：最短路，BFS
解法：对于60%的数据，从小到大枚举点，删除比当前枚举点更大的点
判断最短路径是否小于总油量，如果满足条件退出，
最坏时间复杂度O(N^3)(Dijkstra)，O(NEQ)(SPFA,Q为进队次数);
对于100%的数据，二分答案！
By Satoshi 7.8 2015*/
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
ifstream in("cost.in");
ofstream out("cost.out");
int m,n,start,end;
long long s=0;
long long sum=0;
long long INF=1;
long long limit=0;
vector<int> G[10001],C[10001];
int ans=-1;
bool l[10001]={0},ll[10001]={0};
long long f[10001]={0};
long long W[10001]={0};
class node
{
public:
	int w;
	int text;
}A[10001];
bool com(node a,node b)
{
	if(a.w<b.w)return 1;
	if(a.w==b.w)
	{
		if(a.text<b.text)return 1;
	}
	return 0;
}
long long Dij(int s,int t)
{
	int i;
	priority_queue<pair<int,int> > q;
	//out<<limit<<endl;
	for(i=1;i<=n;i++)
	{
		f[i]=INF;
		l[i]=0;
	}
	q.push(make_pair(-f[s],s));
	f[s]=0;
	l[s]=1;
	if(W[s]<=limit)
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		l[u]=0;
		for(i=0;i<G[u].size();i++)
		{
			int v=G[u][i];
			int c=C[u][i];
			if(W[v]>limit)continue;
			if(f[v]>f[u]+c)
			{
				f[v]=f[u]+c;
				if(!l[v])
				{
					l[v]=1;
					q.push(make_pair(-f[v],v));
				}
			}
		}
	}
	return f[t];
}
void read()
{
	int i,a,b,c;
	INF=INF<<50;
	//out<<INF<<endl;
	in>>n>>m>>start>>end>>s;
	for(i=1;i<=n;i++)
	{
		A[i].text=i;
		ll[i]=1;
		A[i].w=0;
		in>>A[i].w;
		//out<<A[i].w<<' ';
	}
	for(i=1;i<=m;i++)
	{
		in>>a>>b>>c;
		G[a].push_back(b);
		G[b].push_back(a);
		C[a].push_back(c);
		C[b].push_back(c);
	}
}
int tryit(int l,int r)
{
	int mid=(l+r)/2;
	limit=A[mid].w;
	sum=Dij(start,end);
	if(l==r)
	{
		if(sum<=s)out<<A[mid].w<<endl;
		else out<<-1<<endl;
		return 0;
	}
	if(sum<=s)tryit(l,mid);
	else tryit(mid+1,r);
}
void work()
{
	int i,j;
	int pos=0;
	sort(A+1,A+n+1,com);
	for(i=1;i<=n;i++)W[A[i].text]=A[i].w;
	//out<<endl;
	//for(i=1;i<=n;i++)out<<A[i].w<<' ';
	tryit(1,n);
	/*pos=min(A[start].text,A[end].text);
	for(i=1;i<=pos;i++)ll[A[i].text]=0;
	for(i=pos;i<=n;i++)
	{
		ll[A[i].text]=0;
		//if(A[i].text==start||A[i].text==end)continue;
		sum=Dij(start,end);
		if(sum<=s)
		{
			ans=A[i].w;
			break;
		}
	}*/
}
void print()
{
	int i;
	//for(i=1;i<=n;i++)out<<A[i].w<<' '<<A[i].text<<endl;
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	//print();
	return 0;
}