记录编号	71016	评测结果	AAAAAATATA
题目名称	城市	最终得分	80
用户昵称	vector	是否通过	未通过
代码语言	C++	运行时间	2.107 s
提交时间	2013-10-05 16:51:34	内存使用	0.50 MiB

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int f[10010];
int r[10010];
int L,R,res;
int n,m,S,T,E;
 
struct Edge
{
	int to;
	int f;
	Edge(int x,int y)
	{
		to=x;
		f=y;
	}
};
vector<Edge> G[10010];
 
bool Spfa(int M)
{
	queue<int> q;
	long long dis[10010];
	bool vis[10010];
	memset(dis,63,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(S);
	dis[S]=0;
	vis[S]=true;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(int i=0;i<G[t].size();++i)
		{
			Edge *u=&G[t][i];
			if(f[(*u).to]>M)continue;
			if(dis[(*u).to]>dis[t]+(*u).f)
			{
				dis[(*u).to]=dis[t]+(*u).f;
				if(!vis[(*u).to] && dis[(*u).to]<=E)
				{
					vis[(*u).to]=true;
					q.push((*u).to);
				}
			}
		}
		vis[t]=false;
	}
	if(dis[T]<=E)return true;
	else return false;
}
 
int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	scanf("%d %d %d %d %d",&n,&m,&S,&T,&E);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&f[i]);
		R=max(R,f[i]);
	}
	L=max(f[S],f[T]);
	
	for(int i=1;i<=m;++i)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		G[a].push_back(Edge(b,c));
		G[b].push_back(Edge(a,c));
	}
	
	if(!Spfa(R))
	{
		puts("-1");
		return 0;
	}
	
	while(L<=R)
	{
		int M=L+R>>1;
		if(Spfa(M))
		{
			res=M;
			R=M-1;
		}
		else L=M+1;
	}
	
	printf("%d\n",res);
	return 0;
}