记录编号	22097	评测结果	AAAAAAAATA
题目名称	城市	最终得分	90
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	1.771 s
提交时间	2010-11-16 21:38:34	内存使用	0.42 MiB

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAXN=10005;

typedef long long LL;

struct Node
{
	int v,w;
	Node *next;
	Node(int a,int b,Node *c):v(a),w(b),next(c){}
}*adj[MAXN];

inline void add(int u,int v,int w)
{
	adj[u]=new Node(v,w,adj[u]);
	adj[v]=new Node(u,w,adj[v]);
}

inline void Max(int &a,int b)
{
	if (b>a) a=b;
}

int N,M,S,T,V,re=0x7fffffff;
int f[MAXN];
bool CAN;

long long dis[MAXN];
bool in[MAXN];
bool spfa(int mf)
{
	deque<int> q;
	memset(dis,-1,sizeof(dis));
	long long sum=0;
	dis[S]=0;q.push_back(S);in[S]=true;
	while(!q.empty())
	{
		int u;
		while(true)
		{
			u=q.front();
			q.pop_front();
			if (dis[u]<=sum/(q.size()+1)) break;
			else q.push_back(u);
		}
		in[u]=false;
		for(Node *p=adj[u];p;p=p->next)
			if (f[p->v]<=mf&&(dis[p->v]==-1||dis[p->v]>dis[u]+p->w))
			{
				int x=dis[p->v];
				dis[p->v]=dis[u]+p->w;
				if (dis[p->v]<=V)
				{
					if (!in[p->v])
					{
						if (q.empty()||dis[p->v]<dis[q.front()]) q.push_front(p->v);
						else q.push_back(p->v);
						sum+=dis[p->v];
						in[p->v]=true;
					}
					else
						sum=sum+dis[p->v]-x;
					if (p->v==T)
					{
						memset(in,false,sizeof(in));
						return true;
					}					
				}
			}
	}
	return dis[T]!=-1&&dis[T]<=V;
}

int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	scanf("%d%d%d%d%d",&N,&M,&S,&T,&V);
	int l=0,r=0;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",f+i);
		Max(r,f[i]);
	}
	l=f[S];
	while(M--)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if (spfa(mid)) CAN=true,r=mid;
		else l=mid+1;
	}
	if (!spfa(r)) printf("%d\n",-1);
	else 
	{
		if (spfa(l)) printf("%d\n",l);
		else printf("%d\n",r);
	}
	return 0;
}