比赛场次 116
比赛名称 20111110
比赛状态 已结束比赛成绩
开始时间 2011-11-10 08:30:00
结束时间 2011-11-10 11:30:00
开放分组 全部用户
注释介绍
题目名称 城市
输入输出 cost.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarCzb。 AAAAAAAWWA 0.000 s 0.00 MiB 80
Gravatar王者自由 AAAAAAEEEA 0.000 s 0.00 MiB 70
Gravatardonny WWWAAATWTA 0.000 s 0.00 MiB 40
Gravatar日光。 WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatarwk_noi WWWWWWWAWW 0.000 s 0.00 MiB 10
GravatarYeehok WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatar血之侍卫 WWWWWWWAWW 0.000 s 0.00 MiB 10
GravatarQhelDIV WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatar苏轼 WEEEETWAWW 0.000 s 0.00 MiB 10
GravatarTruth.Cirno AWEWEEETTW 0.000 s 0.00 MiB 10
Gravatarhello! WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatar11111111 WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatarreamb WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatarsong WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatar临轩听雨ゐ WWWWWWWAWW 0.000 s 0.00 MiB 10
GravatarTBK WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatarlizhe WWWWWWWWWA 0.000 s 0.00 MiB 10
GravatarDes. WWWWWWWAWW 0.000 s 0.00 MiB 10
Gravatarkaaala C 0.000 s 0.00 MiB 0
GravatarCloud C 0.000 s 0.00 MiB 0
Gravataryifeng WWTTTTEEEW 0.000 s 0.00 MiB 0
Gravatar风华正茂 EMMMMMMMMM 0.000 s 0.00 MiB 0
GravatarMakazeu WWWWWWEEEW 0.000 s 0.00 MiB 0

城市

★★   输入文件:cost.in   输出文件:cost.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】
在某个遥远的国家里,有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
【输出样例1】
8
【输入样例2】
4 4 2 3 3
8
5
6
10
2 1 2
2 4 1
1 3 4
3 4 3
【输出样例2】
-1
【数据规模】


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