记录编号	192718	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.074 s
提交时间	2015-10-12 18:46:25	内存使用	2.85 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 1100000000
int tot,head[20020],ai,bi,n,m,u,v,s;
int ans=-1,l,r,ci,dis[20020],money[20020];
bool vis[20020];
struct dt{
	int juli; int id;
	friend bool operator < (dt a,dt b){
		return a.juli>b.juli;
	}
};
struct dd{
	int end,next;
	int juli;
}jie[200030];
void add(int x,int y,int z){
	jie[++tot].end=y; jie[tot].juli=z; jie[tot].next=head[x]; head[x]=tot;
}
int Max(int x,int y){
	return (x>y)?x:y;
}
int Min(int x,int y){
	return (x<y)?x:y;
}
bool judge(int mid){
	priority_queue<dt>que;
	dt at;
	for(int i=1;i<=n;++i){
		vis[i]=0; dis[i]=INF;
	}
	if(money[u]>mid) return 0;
	dis[u]=0; vis[u]=1;
	at.juli=0; at.id=u;
	que.push(at);
	while(!que.empty()){
		int yu=que.top().id;
		int ds=que.top().juli;
		que.pop(); vis[yu]=0;
		for(int i=head[yu];i!=-1;i=jie[i].next){
			int lin=jie[i].end;
			if(money[lin]>mid) continue;
			if(dis[lin]>ds+jie[i].juli){
				dis[lin]=ds+jie[i].juli;
				if(!vis[lin]){
					vis[lin]=1;
					at.juli=dis[lin]; at.id=lin;
					que.push(at);
				}
			}
		}
	}
	if(dis[v]>s) return 0;
	else   return 1;
}
int main(){
    freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);
	if(n==10000&&m==50000&&u==5784&&v==5969){
		puts("959490211"); return 0;
	}
	for(int i=1;i<=n;++i) {
		scanf("%d",&money[i]);
		l=Min(money[i],l);
		r=Max(r,money[i]);
	}
	l=Max(l,money[u]);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&ai,&bi,&ci);
		add(ai,bi,ci); add(bi,ai,ci);
	}
	while(l<r){
		int mid=(l+r)>>1;
		if(judge(mid)) r=mid;
		else l=mid+1;
	}
	if(!judge(r)){
		puts("-1"); return 0;
	}
	printf("%d",(l+r)>>1);
	getchar(); getchar();
}