记录编号	33499	评测结果	AWAAAAWAWW
题目名称	城市	最终得分	60
用户昵称	Truth.Cirno	是否通过	未通过
代码语言	C++	运行时间	0.398 s
提交时间	2011-11-10 19:58:08	内存使用	114.84 MiB

#include <cstdio>
#include <cstdlib>
#include <memory.h>
using namespace std;

int oil,pay[10001]={0},paynum[10001]={0},way[10001]={0},map[10001][1500]={{0}},dis[10001][1500]={{0}};
bool used[10001]={false};

void swap(int& a,int& b)
{
	int temp;
	temp=a;
	a=b;
	b=temp;
}

void qqsort(int l,int r)
{
	int ll,rr,temp;
	ll=l;
	rr=r;
	temp=pay[rand()%(r-l+1)+l];
	while (ll<=rr)
	{
		while (pay[ll]<temp)
			ll++;
		while (temp<pay[rr])
			rr--;
		if (ll<=rr)
		{
			swap(pay[ll],pay[rr]);
			swap(paynum[ll],paynum[rr]);
			ll++;
			rr--;
		}
	}
	if (l<rr)
		qqsort(l,rr);
	if (ll<r)
		qqsort(ll,r);
}

bool bfs(int st,int en)
{
	int i,tail=0,head=0,que[10000]={0},cost[10000]={0};
	if (used[st])
		return(0);
	que[0]=st;
	used[st]=true;
	while (tail<=head)
	{
		for (i=0;i<way[que[tail]];i++)
		{
			if (!used[map[que[tail]][i]])
			{
				head++;
				cost[head]=cost[tail]+dis[que[tail]][i];
				if (cost[head]>oil)
				{
					head--;
					continue;
				}
				que[head]=map[que[tail]][i];
				used[que[head]]=true;
				if (que[head]==en)
				{
					return(1);
				}
			}
		}
		tail++;
	}
	return(0);
}

int main(void)
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	int i,j,n,m,l,r,st,en,mid,temp,temp2,temp3;
	bool flag,able=false;
	scanf("%d %d %d %d %d\n",&n,&m,&st,&en,&oil);
	for (i=1;i<=n;i++)
	{
		scanf("%d\n",&pay[i]);
		paynum[i]=i;
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d %d %d\n",&temp,&temp2,&temp3);
		flag=false;
		for (j=0;j<way[temp];j++)
			if (map[temp][j]==temp2)
			{
				flag=true;
				if (temp3<dis[temp][j])
					dis[temp][j]=temp3;
			}
		if (flag==false)
		{
			map[temp][way[temp]]=temp2;
			dis[temp][way[temp]]=temp3;
			way[temp]++;
		}
		swap(temp,temp2);
		flag=false;
		for (j=0;j<way[temp];j++)
			if (map[temp][j]==temp2)
			{
				flag=true;
				if (temp3<dis[temp][j])
					dis[temp][j]=temp3;
			}
		if (flag==false)
		{
			map[temp][way[temp]]=temp2;
			dis[temp][way[temp]]=temp3;
			way[temp]++;
		}
	}
	qqsort(1,n);
	l=1;
	r=n;
	mid=(l+r)/2;
	while (l<r)
	{
		memset(used,0,sizeof(used));
		for (i=mid+1;i<=n;i++)
			used[paynum[i]]=true;
		flag=bfs(st,en);
		if (flag)
		{
			able=true;
			r=mid;
		}
		else
			l=mid+1;
		mid=(l+r)/2;
	}
	if (!able)
		printf("-1\n");
	else
		printf("%d\n",pay[mid]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}