记录编号	300732	评测结果	WWWAAAAAAA
题目名称	城市	最终得分	70
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.283 s
提交时间	2016-08-28 20:54:12	内存使用	1.62 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int maxn=10010,maxe=50010;
struct edge{
	int to,prev,dis;
}e[maxe<<1];
struct node{
	int x,g;
	node(int x,int g):x(x),g(g){}
	bool operator<(const node &x)const{
		return g>x.g;
	}
};
void insert(int,int,int);
void Dijkstra();
int n,m,u,v,s,len=0,last[maxn]={0},w[maxn],a[maxn],dis[maxn],x,y,z,l,r,mid,ans;
bool vis[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
#endif
	scanf("%d%d%d%d%d",&n,&m,&u,&v,&s);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);
		insert(y,x,z);
	}
	memcpy(a,w,sizeof(a));
	sort(a+1,a+n+1);
	l=0;r=n;
	while(l<=r){
		mid=(l+r)>>1;
		ans=a[mid];
		Dijkstra();
		if(dis[v]<=s)r=mid-1;
		else l=mid+1;
	}
	if(l>n)a[l]=-1;
	printf("%d",a[l]);
	return 0;
}
void insert(int x,int y,int z){
	e[++len].to=y;
	e[len].dis=z;
	e[len].prev=last[x];
	last[x]=len;
}
void Dijkstra(){
	int x,y;
	memset(vis,0,sizeof(vis));
	memset(dis,63,sizeof(dis));
	dis[u]=0;
	__gnu_pbds::priority_queue<node,less<node>,__gnu_pbds::rc_binomial_heap_tag>heap;
	heap.push(node(u,0));
	while(!heap.empty()){
		node t=heap.top();
		heap.pop();
		x=t.x;
		if(vis[x])continue;
		if(x==v)return;
		vis[x]=true;
		for(int i=last[x];i;i=e[i].prev){
			y=e[i].to;
			if(!vis[y]&&w[y]<=ans&&dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis;
				heap.push(node(y,dis[x]+e[i].dis));
			}
		}
	}
}