← 返回题目列表

AtCoder · icpc2013autumn_c

C. SIRO 挑战

中文机器翻译题面 查看原题

问题陈述

你现在正在和你的朋友二郎一起参加编程竞赛夏令营,他是拉面连锁店SIRO的爱好者。 由于每家SIRO餐厅都有自己美味的拉面,他想在晚上尽可能多地尝试不同的餐厅。 不过,他今晚的时间并不充裕,因为明天一早他还要起床参加训练。 所以他要求你在有限的时间内找出他最多可以去多少家不同的餐馆吃拉面。

该市有 $n$ 个火车站,编号为 $1$ 到 $n$。 $s$ 站是距离营地最近的车站。 $m$ 个车站通过铁路直接相连:您可以在 $c_i$ 分钟内在 $a_i$ 和 $b_i$ 车站之间双向移动。 在这些车站中,有 $l$ 车站附近有一家 SIRO 餐厅。每个车站周围最多有一家SIRO餐厅,车站附近没有餐厅$s$。 二郎在$j_i$车站附近的餐厅吃拉面需要$e_i$分钟。

在车站和附近的 SIRO 餐厅之间来回只需要很短的时间。 您还可以假设二郎不必等待拉面在餐厅上桌。

Jiro 现在在车站 $s$,必须在 $t$ 分钟内返回车站。他能品尝多少种不同的 SIRO?


输入

输入是一系列数据集。数据集的数量不超过 100 美元。每个数据集的格式如下:

$n$ $m$ $l$ $s$ $t$
$a_1$ $b_1$ $c_1$
:
:
$a_m$ $b_m$ $c_m$
$j_1$ $e_1$
:
:
$j_l$ $e_l$

每个数据集的第一行包含五个整数:

  • $n$ 为站点数量,

  • $m$ 为直接连接的站对的数量,

  • $l$ 为 SIRO 餐厅数量,

  • $s$ 为起点站,以及

  • Jiro 的时间限制为 $t$。

以下每行 $m$ 包含三个整数:

  • $a_i$ 和 $b_i$ 用于连接的站,以及

  • $c_i$ 表示在两个站点之间移动所需的时间。

以下每行 $l$ 包含两个整数:

  • $j_i$ 为 SIRO 餐厅所在的车站,以及

  • $e_i$ 表示 Jiro 在餐厅吃饭所花费的时间。

输入的结尾由带有五个零的行指示,该行不包含在数据集中。

数据集满足以下约束:

  • $2 \le n \le 300$

  • $1 \le m \le 5{,}000$

  • $1 \le l \le 16$

  • $1 \le s \le n$

  • $1 \le t \le 100{,}000$

  • $1 \le a_i, b_i \le n$

  • $1 \le c_i \le 1{,}000$

  • $1 \le j_i \le n$

  • $1 \le e_i \le 15$

  • $s \ne j_i$

  • $j_i$ 是不同的。

  • $a_i \ne b_i$

  • $(a_i, b_i) \ne (a_j, b_j)$ 和 $(a_i, b_i) \ne (b_j, a_j)$ 对于任何 $i \ne j$

请注意,可能有一些车站无法从起点 $s$ 到达。

输出

对于每个数据集,输出 Jiro 在限定时间内可以去的不同餐厅的最大数量。


示例输入

2 1 1 1 10
1 2 3
2 4
2 1 1 1 9
1 2 3
2 4
4 2 2 4 50
1 2 5
3 4 5
2 15
3 15
4 6 3 1 29
1 2 20
3 2 10
4 1 5
3 1 5
2 4 3
3 4 4
2 1
4 5
3 3
0 0 0 0 0

样本输入的输出

1
0
1
3