Skip to content
Sign in

建設事業 2 (Construction Project 2)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

JOI 国には \(N\) 個の駅があり，\(1\) から \(N\) までの番号が付けられている．また，JOI 国には \(M\) 本の鉄道路線があり，\(1\) から \(M\) までの番号が付けられている．鉄道路線 \(i\) (\(1 \leqq i \leqq M\)) は駅 \(A_i\) と駅 \(B_i\) を双方向に結んでおり，その移動には \(C_i\) 分を要する．

JOI 国の大臣であるあなたは，以下のように鉄道路線を新たに \(1\) 本建設することにした．

  • \(1 \leqq u < v \leqq N\) を満たす整数 \(u, v\) を選ぶ．駅 \(u\) と駅 \(v\) を双方向に結び，その移動に \(L\) 分を要する鉄道路線を JOI 国に建設する．すでに駅 \(u\) と駅 \(v\) を双方向に結ぶ鉄道路線があってもよいことに注意せよ．

あなたが建設を行った後に，駅 \(S\) から駅 \(T\) までいくつかの鉄道路線を用いて \(K\) 分以内に移動できるようになっている場合，国王は喜ぶ．なお，鉄道路線の乗り換え時間や待ち時間は考えないものとする．

建設する際の \(2\) つの整数 \(u, v\) の選び方は \(\frac{N \left( N - 1 \right)}{2}\) 通りあるが，このうち国王が喜ぶような選び方が何通りあるかあなたは知りたい．

駅と鉄道路線，国王の要望の情報が与えられたとき，国王が喜ぶような \(2\) つの整数の選び方が何通りあるかを求めるプログラムを作成せよ．

Input

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\)
\(S\) \(T\) \(L\) \(K\)
\(A_1\) \(B_1\) \(C_1\)
\(A_2\) \(B_2\) \(C_2\)
\(\vdots\)
\(A_M\) \(B_M\) \(C_M\)

Output

標準出力に，国王が喜ぶような \(2\) つの整数の選び方が何通りあるかを \(1\) 行で出力せよ．

Constraints

  • \(2 \leqq N \leqq 200\,000\)．
  • \(1 \leqq M \leqq 200\,000\)．
  • \(1 \leqq S < T \leqq N\)．
  • \(1 \leqq L \leqq 10^{9}\)．
  • \(1 \leqq K \leqq 10^{15}\)．
  • \(1 \leqq A_i < B_i \leqq N\) (\(1 \leqq i \leqq M\))．
  • \((A_i, B_i) \neq (A_j, B_j)\) (\(1 \leqq i < j \leqq M\))．
  • \(1 \leqq C_i \leqq 10^9\) (\(1 \leqq i \leqq M\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(8\) 点) \(L = 1\)，\(K = 2\)，\(C_i = 1\) (\(1 \leqq i \leqq M\))．
  2. (\(16\) 点) \(N \leqq 50\)，\(M \leqq 50\)．
  3. (\(29\) 点) \(N \leqq 3\,000\)，\(M \leqq 3\,000\)．
  4. (\(47\) 点) 追加の制約はない．

Examples

Sample input 1
7 8
6 7 1 2
1 2 1
1 6 1
2 3 1
2 4 1
3 5 1
3 7 1
4 5 1
5 6 1
Sample output 1
4

たとえば，あなたが \(u = 3, v = 6\) と選んだとする．駅 \(3\) と駅 \(6\) を双方向に結び，その移動に \(1\) 分を要する鉄道路線が JOI 国に建設される．

このとき，以下のようにして，駅 \(6\) から駅 \(7\) まで鉄道路線を用いて \(2\) 分で移動できる．駅 \(6\) から駅 \(7\) まで \(2\) 分以内に移動できるようになっているため，国王は喜ぶ．

  1. 駅 \(3\) と駅 \(6\) を双方向に結ぶ路線を用いて，駅 \(6\) から駅 \(3\) に移動する．これには \(1\) 分を要する．
  2. 駅 \(3\) と駅 \(7\) を双方向に結ぶ路線を用いて，駅 \(3\) から駅 \(7\) に移動する．これには \(1\) 分を要する．

国王が喜ぶような \(2\) つの整数の選び方はこの場合を含めて \(4\) 通りある．したがって，\(4\) を出力する．

この入力例は小課題 \(1,2,3,4\) の制約を満たす．

Sample input 2
3 2
1 3 1 2
1 2 1
2 3 1
Sample output 2
3

あなたがどのように \(2\) つの整数を選んでも，国王は喜ぶ．すなわち，国王が喜ぶような \(2\) つの整数の選び方は \(3\) 通りある．したがって，\(3\) を出力する．

この入力例は小課題 \(1,2,3,4\) の制約を満たす．

Sample input 3
6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000
Sample output 3
0

あなたがどのように \(2\) つの整数を選んでも，国王が喜ぶことはない．したがって，\(0\) を出力する．

この入力例は小課題 \(2,3,4\) の制約を満たす．

Sample input 4
18 21
4 8 678730772 3000000062
5 13 805281073
8 17 80983648
3 8 996533440
10 16 514277428
2 5 57914340
6 11 966149890
8 12 532734310
2 9 188599710
2 3 966306014
12 16 656457780
16 18 662633078
1 15 698078877
2 8 665665772
2 6 652261981
14 15 712798281
7 13 571169114
13 14 860543313
6 7 454251187
9 14 293590683
6 14 959532841
3 11 591245645
Sample output 4
16

この入力例は小課題 \(2,3,4\) の制約を満たす．

Notes

JOI 2024 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source