记录编号	169702	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.340 s
提交时间	2015-07-10 11:42:16	内存使用	5.07 MiB

#include<cstdio>
#include<deque>
#include<iostream>
#include<queue>
using namespace std;
int n,m,u,v,s,sp[10010];
int f[10010];
int maxn=0x7fffffff;
int ma=0,mi=0x7fffffff;
deque<int> sw[10010];
deque<int> p[10010];
bool SPFA(int cost)
{
	priority_queue<pair<int, int> > Q;
	bool inq[10010]={0};
	inq[u]=1;
	for(int i=1;i<=n;i++)
		sp[i]=maxn;
	sp[u]=0;
	Q.push(make_pair(-sp[u],u));
	while(!Q.empty())
	{
		int x=Q.top().second;Q.pop();inq[x]=0;
		for(int i=0;i<sw[x].size();i++)
		{
			int fr=sw[x][i];
			if(f[fr]>cost) continue;
			int lo=p[x][i];
			if(sp[x]+lo<sp[fr])
			{
				sp[fr]=sp[x]+lo;
				if(inq[fr]==0)
				{
					inq[fr]=1;
					Q.push(make_pair(-sp[fr],fr));
				}
			}
		}
	}
	if(sp[v]>s) return 0;
	else return 1;
}
int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&f[i]);
		mi=min(f[i],mi);
		ma=max(f[i],ma);
	}
	mi=max(mi,f[u]);
	int fr,to,lo;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&fr,&to,&lo);
		sw[fr].push_back(to);p[fr].push_back(lo);
		sw[to].push_back(fr);p[to].push_back(lo);
	}
	//cout<<ma<<" "<<mi<<endl;
	if(SPFA(ma)==0) 
	{
		printf("-1");
		return 0;
	}
	while(mi<ma)
	{
		int mid=(ma+mi)/2;
		if(SPFA(mid)==0) mi=mid+1;
		else ma=mid;
	}
	printf("%d",mi);
	return 0;
}