C - ウサギとカメ Editorial /

Time Limit: 7 sec / Memory Limit: 256 MB

問題文

ウサギとカメが ARC 山でレースをすることになった。

ARC 山には N 個の中継点があり、中継点には 1 から N まで番号が付けられている。また異なる 2 つの中継点間を結ぶ道が M 本ある。どの 2 つの異なる道に関しても、結んでいる 2 つの中継点同士が一致することはない。道ごとに長さが定まっている。また、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