记录编号	71264	评测结果	AAAAAAAAAA
题目名称	城市	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2013-10-06 21:06:10	内存使用	0.63 MiB

#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
ifstream fin("cost.in");
ofstream fout("cost.out");
class woca
{
public:
	int x;
	int y;
};//x下一个节点，y为权值
vector<woca> adj[10010];
int n,m,u,v,s;
long long cost[10010],FZ[10010];
int dist[10010];bool CP[10010];
bool operator<(woca n,woca m)
{
	if(n.y<m.y)
		return 0;
	else
		return 1;
}
bool Dijk(int x)
{
	if(cost[u]>x) return false;
	woca p,e;
	int j;
	priority_queue<woca> q;
	for(j=1;j<=n;j++)
		dist[j]=1100000000;
	memset(CP,0,sizeof(CP));
	dist[u]=0;e.x=u;e.y=0;
	q.push(e);
	while(!q.empty())
	{
		p=q.top();q.pop();
		if(CP[p.x]==0)
		{
			CP[p.x]=1;
		for(unsigned int i=0;i<adj[p.x].size();i++)
		{
			if(cost[adj[p.x][i].x]>x)continue;
			if(!CP[adj[p.x][i].x]&&dist[adj[p.x][i].x]>dist[p.x]+adj[p.x][i].y)
			{
				dist[adj[p.x][i].x]=dist[p.x]+adj[p.x][i].y;
				e.x=adj[p.x][i].x;
				e.y=dist[adj[p.x][i].x];
				q.push(e);
			}
		}
		}
	}
	if(dist[v]<=s)return true;
	return false;
}
int main()
{
	fin>>n>>m>>u>>v>>s;
	int i,A,B,C,MID;
	int ANS;
	woca temp,flag;
	for(i=1;i<=n;i++)
	{
		fin>>FZ[i];
		cost[i]=FZ[i];
	}
	for(i=1;i<=m;i++)
	{
		fin>>A>>B>>C;
		temp.x=B;
		temp.y=C;
		adj[A].push_back(temp);
		flag.x=A;
		flag.y=C;
		adj[B].push_back(flag);
	}
	sort(FZ+1,FZ+n+1);
	int L=1,R=n;
	if(!Dijk(FZ[n]))
	{
		fout<<-1<<endl;
		return 0;
	}
	while(L<=R)
	{
		MID=(L+R)>>1;
	    if(Dijk(FZ[MID]))
		{
			ANS=FZ[MID];
			R=MID-1;
		}
		else
		{
			L=MID+1;
		}
	}//二分
	fout<<ANS<<endl;
	return 0;
}