记录编号	22037	评测结果	WWAAAWEEEA
题目名称	城市	最终得分	40
用户昵称	lc	是否通过	未通过
代码语言	C++	运行时间	0.427 s
提交时间	2010-11-16 19:01:01	内存使用	4.17 MiB

#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn = 1010;
long long INF;
long long Dis[maxn];
bool Mark[maxn];
int N,M,S,T,Limit;
int Cost[maxn],C[maxn]; int Gra[maxn][maxn];
 
 
 
bool cmp(const int x,const int y)
{
	return x < y;
}
 
 
void prep()
{
	scanf("%d%d%d%d%d",&N,&M,&S,&T,&Limit);
	for (int i=1; i<=N; i++) scanf("%d",&Cost[i]);
	for (int i=1; i<=N; i++)
		for (int j=1; j<=N; j++)
			Gra[i][j] = 2000000000;
	for (int i=1; i<=M; i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		Gra[x][y] = c < Gra[x][y] ? c : Gra[x][y];
	}
}
 
bool Can(int LimitCost)
{
	if (Cost[S]>LimitCost || Cost[T]>LimitCost) return false;
	for (int i=1; i<=N; i++) Dis[i] = INF; Dis[S] = 0;
	for (int i=1; i<=N; i++) Mark[i] = false;
	for (int i=1; i<=N; i++)
	{
		int k; long long Mink = INF;
		for (int j=1; j<=N; j++)
			if (!Mark[j] && Dis[j] <Mink && Cost[j]<=LimitCost)
			{
				Mink = Dis[j]; k = j;
			}
		Mark[k] = true;
		for (int j=1; j<=N; j++)
			if (Dis[k] + Gra[k][j] <Dis[j] && Cost[j]<=LimitCost)
			{
				Dis[j] = Dis[k] + Gra[k][j];
			}
	}
	
	return (Dis[T]<=(long long)Limit);
}
 
void work()
{
	INF = 100000000;
	INF = INF * INF;
	
	for (int i=1; i<=N; i++) C[i] = Cost[i];
	sort(C+1,C+1+N,cmp);
	
	int L = 1,R = N;
	if (!Can(C[R]))
	{
		printf("-1\n"); return;
	}
	if (Can(C[L]))
	{
		printf("%d\n",C[L]); return;
	}
	while (R - L >1)
	{
		int Mid = (L + R) / 2;
		if (Can(C[Mid])) R = Mid; else L = Mid;
	}
	printf("%d\n",C[R]);
}
 
int main()
{
	freopen("cost.in","r",stdin);
	freopen("cost.out","w",stdout);
	prep();
	work();
	return 0;
}