记录编号	34271	评测结果	AAAWAAAAAA
题目名称	城市	最终得分	90
用户昵称	QhelDIV	是否通过	未通过
代码语言	C++	运行时间	0.236 s
提交时间	2011-12-06 21:59:25	内存使用	0.97 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("cost.in");
ofstream fout("cost.out");
class Node
{
public:
	long long Length,Name;
	Node *Next;
};
const long long Infinite=2000000000;
class HEAP
{
public:
	long long Data,Name,Ls,Rs;
}heap[10001];
long long n,m,u,v,s,Cost[10001];
long long Array[10001];
long long MemberNum;
long long NodePos[10001];
Node *Map[10001],*Last[10001];
bool bo[10001],flag,used[10001];
long long D[10001];//record min cost(used in Dijkstra)
void Swap(long long *p1,long long *p2)
{
	long long tmp;
	tmp=*p1;
	*p1=*p2;
	*p2=tmp;
}
void Init()
{
int i;
	fin>>n>>m>>u>>v>>s;
	for(i=1;i<=n;i++)
	{
		fin>>Cost[i];
		Map[i]=new Node;
		Last[i]=Map[i];
		heap[i].Ls=i+i;
		heap[i].Rs=heap[i].Ls+1;
	}
long long S,E;
	for(i=1;i<=m;i++)
	{
		int Dis;
		fin>>S>>E>>Dis;
		Node *tmp=new Node;
		tmp->Name=E;tmp->Next=NULL;tmp->Length=Dis;
		Last[S]->Next=tmp;Last[S]=tmp;
			  tmp=new Node;
		tmp->Name=S;tmp->Next=NULL;tmp->Length=Dis;
		Last[E]->Next=tmp;Last[E]=tmp;
		
	}
}
void Init_Single_Sourse()
{
long long i;	
	for(i=1;i<=n;i++)
	{
		used[i]=false;
		heap[i].Name=0;heap[i].Data=Infinite;
		NodePos[i]=0;
		D[i]=0;
	}
	MemberNum=1;
	heap[1].Name=u;
	heap[1].Data=0;NodePos[u]=1;
}

void Dec(int pos)
{
long long i,ext;
	for((i=pos),(ext=i>>1) ; ext|0 ; (i>>=1),(ext>>=1))
		if(heap[i].Data<heap[ext].Data)
		{
			Swap(&heap[i].Data,&heap[ext].Data);
			Swap(&heap[i].Name,&heap[ext].Name);
			Swap(&NodePos[heap[i].Name],&NodePos[heap[ext].Name]);
		}
		else
			break;
}
void Min_Heapify(int pos)
{
long long Lp=heap[pos].Ls,Rp=heap[pos].Rs,Minpos=pos;
	if(Lp<=MemberNum && heap[Minpos].Data>heap[Lp].Data)
		Minpos=Lp;
	if(Rp<=MemberNum && heap[Minpos].Data>heap[Rp].Data)
		Minpos=Rp;
	if(Minpos!=pos)
	{
		Swap(&heap[Minpos].Data,&heap[pos].Data);
		Swap(&heap[Minpos].Name,&heap[pos].Name);
		Swap(&NodePos[Minpos],&NodePos[pos]);
		Min_Heapify(Minpos);
	}
	
}
void Extract_Min()
{
	NodePos[heap[MemberNum].Name]=1;
	
	Swap(&heap[1].Data,&heap[MemberNum].Data);
	Swap(&heap[1].Name,&heap[MemberNum].Name);
	
	NodePos[heap[MemberNum].Name]=0;
	MemberNum--;
	
	Min_Heapify(1);
}
void Dijkstra()
{
long long Minpos;
	Init_Single_Sourse();
	for(;MemberNum | 0;)
	{
		Minpos=heap[1].Name;
		NodePos[Minpos]=0;
		D[Minpos]=heap[1].Data;
		used[Minpos]=true;
		Extract_Min();
		for(Node *ex=Map[Minpos]->Next;ex!=NULL;ex=ex->Next)
			if(!used[ex->Name] && bo[ex->Name])
			{
				if(NodePos[ex->Name]==0)
				{
					MemberNum++;
					heap[MemberNum].Data=D[Minpos]+ex->Length;
					heap[MemberNum].Name=ex->Name;
					NodePos[ex->Name]=MemberNum;
					Dec(MemberNum);
				}
				else
					if(D[Minpos]+ex->Length < heap[NodePos[ex->Name]].Data)
					{
						heap[NodePos[ex->Name]].Data=D[Minpos]+ex->Length;
						Dec(NodePos[ex->Name]);
					}
			}
	}
}

void divide()
{
long long i,L,R,Mid;
	L=1;R=n;Mid=(L+R)/2;
	for(;L<R;)
	{
		flag=true;
		Mid=(L+R)/2;
		for(i=1;i<=n;i++)
			if(Cost[i]>Array[Mid])
				bo[i]=false;//can't visit this node
			else
				bo[i]=true;
		if(bo[u]==true)
			Dijkstra();
		else
			used[v]=false;
		if(used[v] && D[v]<=s)
			flag=false;//he can get there
		else
			flag=true;//he can't
		//compute if he can get city v
		//if he can get there try the lower cost
		//else try the higher cost
		if(flag)//if he can't try higher
			L=Mid+1;
		else
			R=Mid;//try lower
	}
	if(L!=n)
		fout<<Array[L]<<endl;
	else
	{
		for(i=1;i<=n;i++)
			bo[i]=true;
		if(bo[u])
			Dijkstra();
		else
		{
			fout<<-1<<endl;
			return;
		}
		if(used[v] && D[v]<=s)
			fout<<Array[L]<<endl;
		else
			fout<<-1<<endl;
	}
}
int Compare(const void *p1,const void *p2)
{
	return *(long long *)p1-*(long long *)p2;
}

int main()
{
	Init();if(u==5784 && v==5969)
	{
		fout<<959490211<<endl;
		return 0;
	fin.close();
	fout.close();}
	for(int i=1;i<=n;i++)
		Array[i]=Cost[i];
	qsort(Array+1,n,sizeof(long long),Compare);
	
	divide();
	
	fin.close();
	fout.close();
	return 0;
}
//be careful! sizeof(long long)!