记录编号	36587	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.383 s
提交时间	2012-03-15 08:38:49	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
 
using namespace std;
 
const int oo=~0u>>2;
 
struct edge
{
	int t,cost;
	edge *next;
	edge(int _t,int _cost,edge *_next):t(_t),cost(_cost),next(_next){}
}*Map[10010];
 
int N,M,U,V,S,F[10010];
 
void addedge(int s,int t,int cost)
{
	Map[s]=new edge(t,cost,Map[s]);
	Map[t]=new edge(s,cost,Map[t]);
}
 
bool djs(int x)
{
	bool vis[10010];
	int dist[10010];
	priority_queue<pair<int,int> >heap;
	if(F[U]>x)
		return true;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=N;i++)
		dist[i]=oo;
	dist[U]=0;
	heap.push(make_pair(0,U));
	while(!heap.empty())
	{
		int u=heap.top().second;
		heap.pop();
		if(!vis[u])
		{
			vis[u]=true;
			for(edge *p=Map[u];p;p=p->next)
			{
				int t=p->t,cost=p->cost;
				if(F[t]>x)
					continue;
				if(!vis[t]&&dist[t]>dist[u]+cost)
				{
					dist[t]=dist[u]+cost;
					heap.push(make_pair(-dist[t],t));
				}
			}
		}
	}
	if(dist[V]>S)
		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,&U,&V,&S);
	int l,r;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&F[i]);
		if(F[i]>r)
			r=F[i];
		if(F[i]<l)
			l=F[i];
	}
	for(int i=1;i<=M;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
	if(djs(r))
	{
		printf("-1\n");
		return 0;
	}
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(!djs(mid))
			r=mid;
		else
			l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}