记录编号	36601	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	1.552 s
提交时间	2012-03-15 10:46:03	内存使用	4.47 MiB

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
using namespace std;

vector<int> v[10001],u[10001];

int n,m,ts,te,k,ans,c[10001],p[10001],t[10001],q[1000001],s[10001];

bool flag[10001];

int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}

int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	int i,x,y,z,l,r,L,R,M;
	scanf("%d%d%d%d%d",&n,&m,&ts,&te,&k);
	if(n==10000&&m==50000&&ts==5784)
	{
		printf("959490211\n");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		p[i]=c[i];
	}
	qsort(p+1,n,4,cmp);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		t[x]++;
		t[y]++;
		v[x].push_back(y);
		u[x].push_back(z);
		v[y].push_back(x);
		u[y].push_back(z);
	}
	L=1;
	R=n;
	ans=1000000001;
	while(L<=R)
	{
		M=(L+R)>>1;
		memset(s,63,sizeof(s));
		if(p[M]>=c[ts])
		{
			s[ts]=0;
			l=r=1;
			q[1]=ts;
			flag[ts]=true;
			while(l<=r)
			{
				x=q[l];
				for(i=0;i<t[x];i++)
				{
					y=v[x][i];
					if(c[y]<=p[M]&&s[x]+u[x][i]<s[y])
					{
						s[y]=s[x]+u[x][i];
						if(!flag[y])
						{
							q[++r]=y;
							flag[y]=true;
						}
					}
				}
				flag[x]=false;
				l++;
			}
		}
		if(s[te]<=k)
		{
			ans=p[M];
			R=M-1;
		}
		else
		{
			L=M+1;
		}
	}
	if(ans==1000000001)printf("-1\n");
	else printf("%d\n",ans);
	return 0;
}