记录编号	36666	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.279 s
提交时间	2012-03-16 13:07:42	内存使用	0.64 MiB

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN=10001;
const int INF=1100000000;
int Cost[MAXN],BS[MAXN];
int N,M,S,B,E;
vector<int> Map[MAXN];
vector<int>Val[MAXN];

inline void init()
{
	scanf("%d %d %d %d %d\n",&N,&M,&B,&E,&S);
	for(int i=1;i<=N;i++)
	{
		scanf("%d\n",&Cost[i]);
		BS[i]=Cost[i];
	}
	sort(BS+1,BS+N+1);
	int a,b,v;
	for(int i=1;i<=M;i++)
	{
		scanf("%d %d %d\n",&a,&b,&v);
		Map[a].push_back(b);
		Map[b].push_back(a);
		Val[a].push_back(v);
		Val[b].push_back(v);
	}
}

priority_queue<pair<int,int> > PQ;
int Used[MAXN];
int Dist[MAXN];

inline bool SP(int x)
/*Dijkstra+Heap Code From Kaaala.   Thanks for Kaaala!!*/
{
	if(Cost[B]>x) return false;
	for(int i=1;i<=N;i++) {Used[i]=0,Dist[i]=INF;}
	Dist[B]=0;
	PQ.push(make_pair(0,B));
	int u,v,cost;
	while(!PQ.empty())
	{
		u=PQ.top().second;
		PQ.pop();
		if(!Used[u])
		{
			Used[u]=1;
			for(unsigned int i=0;i<Map[u].size();i++)
			{
				v=Map[u][i];
				cost=Val[u][i];
				if(Cost[v]>x) continue;
				if(!Used[v]&&Dist[v]-Dist[u]>cost)
				{
					Dist[v]=Dist[u]+cost;
					PQ.push(make_pair(-Dist[v],v));
				}
			}
		}
	}
	if(Dist[E]>S) return false;
	return true;
}

inline void solve()
{
	int L=1,R=N;
	int Mid;
	if(!SP(BS[N])) {printf("-1\n");return;}
	int Ans;
	bool flag;
	while(L<=R)
	{
		Mid=(L+R)>>1;
		flag=SP(BS[Mid]);
		if(flag)
		{
			Ans=BS[Mid];
			R=Mid-1;
		}
		else L=Mid+1;
	}
	printf("%d\n",Ans);
}

int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	init();
	solve();
	return 0;
}