在某个遥远的国家里，有n个城市。编号为1，2，3，……，n。
这个国家的政府修建了m条双向的公路。每条公路连接着两个城市。沿着某条公路，开车从一个城市到另一个城市，需要花费一定的汽油。
开车每经过一个城市，都会被收取一定的费用（包括起点和终点城市）。所有的收费站都在城市中，在城市间的公路上没有任何的收费站。
小红现在要开车从城市u到城市v(1<=u，v<=n)。她的车最多可以装下s升的汽油。在出发的时候，车的油箱是满的，并且她在路上不想加油。
在路上，每经过一个城市，她要交一定的费用。如果她某次交的费用比较多，她的心情就会变得很糟。所以她想知道，在她能到达目的地的前提下，她交的费用中最多的一次最少是多少。这个问题对于她来说太难了，于是她找到了聪明的你，你能帮帮她吗？

    第一行5个正整数，n，m，u，v，s。分别表示有n个城市，m条公路，从城市u到城市v，车的油箱的容量为s升。
接下来有n行，每行1个正整数，fi。表示经过城市i，需要交费fi元。
再接下来有m行，每行3个正整数，ai,bi,ci(1<=ai,bi<=n)。表示城市ai和城市bi之间有一条公路，如果从城市ai到城市bi,或者从城市bi到城市ai，需要用ci升汽油。

    仅一个整数，表示小红交费最多的一次的最小值。
如果她无法到达城市v，输出-1。

【输入样例1】

4 4 2 3 8
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

【输入样例2】

4 4 2 3 3
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3

【输出样例1】

8

【输出样例2】

-1

    对于60%的数据，满足n<=200，m<=10000，s<=200
对于100%的数据，满足n<=10000，m<=50000，s<=1000000000
对于100%的数据，满足ci<=1000000000，fi<=1000000000，可能有两条边连接着相同的城市。

题解：

题目说求交费最多的一次的最小值，所以就要二分答案
在spfa中判断一下当前答案是否合法，如果合法，往更大的方向枚举答案
我spfa里面传的是二分的答案

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
ll first[233333], next[233333], d[233333], tot, f[233333], inf = 21474836;
bool used[233333];
struct edge
{
	int from, to;
	ll cost;
}es[233333];
deque<int> q;
void init()
{
	memset(d, 0x3f, sizeof(d));
	memset(first, -1, sizeof(first));
	tot = 0;
}
void build(int f, int t, ll d)
{
	es[++tot] = (edge){f, t, d};
	next[tot] = first[f];
	first[f] = tot;
}
int n, u;
void spfa(int ff)
{
	memset(d, 0x3f, sizeof(d));
	if(f[u] > ff)
		return ;
	d[u] = 0;
	q.push_front(u);
	used[u] = 1;
	while(!q.empty())
	{
		int su = q.front();
		used[su] = 0;
		q.pop_front();
		for(int i = first[su];i != -1;i = next[i])
		{
			int v = es[i].to;
			if(f[v] > ff)
				continue;
			if(d[v] > d[su] + es[i].cost)
			{
				d[v] = d[su] + es[i].cost;
				if(!used[v])
				{
					if(!q.empty() && d[v] < d[q.front()])
						q.push_front(v);
					else
						q.push_back(v);
					used[v] = 1;
				}
			}
		}
	}
}
int main()
{
	init();
	int m, v, s;
	scanf("%d%d%d%d%d", &n, &m, &u, &v, &s);
	ll l = inf, r = -1;
	for(int i = 1;i <= n;i ++)
	{
		scanf("%I64d", &f[i]);
		r = max(r, f[i]);
		l = min(l, f[i]);
	}
	for(int i = 1;i <= m;i ++)
	{
		int f, t;
		ll d;
		scanf("%d%d%I64d", &f, &t, &d);
		build(f, t, d);
		build(t, f, d);
	}
	spfa(r);
	if(d[v] > s)
	{
		cout<<-1<<endl;
		return 0;
	}
	int ans = inf;
	while(r-1 > l)
	{
		int mid = (l + r)/2;
		spfa(mid);
//		cout<<l<<" "<<r<<" "<<mid<<" "<<d[v]<<endl;
		if(d[v] > s)
			l = mid;
		else
			r = mid, ans = mid;
	}
	spfa(l);
	if(d[v] < s)
		ans = l;
	else
		ans = r;
	if(ans == inf)
		ans = -1;
	cout<<ans<<endl;
	return 0;
}