← 返回题目列表

Codeforces · 144/D

D. 导弹发射井

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

一个名为 Berland 的国家由 n 个城市组成,城市编号为 1 到 n 的整数。其中一些由双向道路连接。每条路都有一定的长度。通过这些道路,从每个城市到任何其他城市都有一条路径。根据一些超级杜珀文件,伯兰德受到超级杜珀导弹的保护。超级骗子秘密导弹发射井的确切位置一直保密,但鲍勃设法掌握了该信息。该信息表明,所有筒仓都位于距首都 l 处。首都位于编号为s的城市。

文件给出了正式的定义:超级秘密导弹发射井位于某个地方(可以是城市,也可以是道路上的一个点),当且仅当沿着该国道路从这个地方到首都的最短距离恰好等于l。

鲍勃想知道伯兰德有多少个导弹发射井,以便将信息出售给敌方间谍。帮助鲍勃。

输入

第一行包含三个整数 n、m 和 s (2 ≤ n ≤ 105, $$n-1 \leq m \leq \min(10^5, \frac{n(n-1)}{2})$$, 1 ≤ s ≤ n) — 相应地,城市数量、国家道路数量和首都数量。首都是城市编号。 s。

然后 m 行包含道路的描述。每条道路均由三个整数 vi、ui、wi(1 ≤ vi、ui ≤ n、vi ≠ ui、1 ≤ wi ≤ 1000)描述,其中 vi、ui 是该道路所连接城市的编号,wi 是该道路的长度。最后输入行包含整数 l (0 ≤ l ≤ 109) — 从首都到导弹发射井的距离。保证:

- 任意两个城市之间不存在超过一条道路;
- 每条道路连接两个不同的城市;
- 从每个城市至少有一条路可以通过公路到达任何其他城市。

输出

打印单个数字 — 位于 Berland 的 Super Duper 秘密导弹发射井的数量。

示例

输入 #1

4 6 1
1 2 1
1 3 3
2 3 1
2 4 1
3 4 1
1 4 2
2

输出 #1

3

输入 #2

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

输出 #2

3

注意

在第一个样本中,筒仓位于城市 3 和 4 以及道路 (1, 3) 上,距城市 1 的距离为 2(相应地,距城市 3 的距离为 1)。

在第二个样本中,一个导弹发射井位于道路中间 (1, 2)。道路 (4, 5) 上还有两个筒仓,在前往城市 5 的方向上距城市 4 的距离为 3,以及从城市 5 到城市 4 的距离为 3。