← 返回题目列表

AtCoder · arc025_3

C. 兔子和乌龟

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

問題文

兔子和乌龟将在ARC山上进行一场比赛。

ARC在山上 有 N 个中继点,中继点有 编号至 1 它们的编号最大为 N 。也不同 2 连接两个中继点的道路 M 有一本书。其中 2 甚至两条不同的路径也是相连的。 2 两个中继点永远不匹配。每条路径都有固定的长度。另外,Mt. ARC 上有哪些地点? 2 可以通过多条道路在两个不同的中继点之间来回。

在比赛中,目的地是从接力点中选择的。 A,兔子的起点 B, 海龟的起点 选择 C 。A,B,C 是中继点之一。 1 必须是A,B,C 必须彼此不同。比赛开始后,兔子会 R 米每秒 T 前往目的地(以米为单位)。

乌龟以最佳方式移动,这样无论兔子使用哪条路线,它都会跟随乌龟到达目的地。 A,B,C 设置 ( 我想知道总共有多少个A,B,C) 。


入力

输入是按以下格式从标准输入给出的。

N M R T
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M
  • 1 行显示中继点数。 N (3 ≦ N ≦ 2,500),道路数量 M (2 ≦ M ≦ 3,000),兔子速度 R (1 ≦ R ≦ 200) 和海龟速度 在 T (1 ≦ T ≦ 200) 用空格分隔。
  • 2 从行 M 行中,给出了有关路径的信息。其中 i 排队 i 是 它可能以 2 两个中继点 a_i,b_i (1 ≦ a_i < b_i ≦ N) 长度是 c_i (1 ≦ c_i ≦ 100) 代表米。

出力

组合总数 在 1 行输出。在输出末尾插入换行符。


入力例1

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

出力例1

2

下面 2 街道是可能的。

  • (目的地,兔子的起点,乌龟的起点)(2, 4, 1),海龟直接前往目的地。 4 秒后到达。另一方面,无论兔子走哪条路,至少 需要 4.5 秒。
  • (目的地,兔子的起点,乌龟的起点)(4, 3, 2),海龟直接前往目的地。 4 秒后到达。另一方面,无论兔子走哪条路,至少 需要 4.5 秒。

超过 2 就是这样。顺便说一句,(目的地,兔子的起点,乌龟的起点)是(1, 4, 3),为了让兔子和乌龟都到达目的地, 需要超过 3 秒。如果它们以最佳方式彼此移动,它们将同时到达,因此不满足条件。


入力例2

5 4 7 7
1 2 1
2 3 1
3 4 1
4 5 1

出力例2

26