레이팅 미적용JOI 国にはN 個の駅があり,1 からN までの番号が付けられている.また,JOI 国にはM 本の鉄道路線
があり,1 からM までの番号が付けられている.鉄道路線i (1 ≦i ≦M) は駅Ai と駅Bi を双方向に結んで
おり,その移動にはCi 分を要する.
JOI 国の大臣であるあなたは,以下のように鉄道路線を新たに1 本建設することにした.
• 1 ≦u < v ≦N を満たす整数u, v を選ぶ.駅u と駅v を双方向に結び,その移動にL 分を要する鉄
道路線をJOI 国に建設する.すでに駅u と駅v を双方向に結ぶ鉄道路線があってもよいことに注意
せよ.
あなたが建設を行った後に,駅S から駅T までいくつかの鉄道路線を用いてK 分以内に移動できるよう
になっている場合,国王は喜ぶ.なお,鉄道路線の乗り換え時間や待ち時間は考えないものとする.
建設する際の2 つの整数u, v の選び方はN(N−1)
2
通りあるが,このうち国王が喜ぶような選び方が何通り
あるかあなたは知りたい.
駅と鉄道路線,国王の要望の情報が与えられたとき,国王が喜ぶような2 つの整数の選び方が何通りある
かを求めるプログラムを作成せよ.
• 2 ≦N ≦200 000.
• 1 ≦M ≦200 000.
• 1 ≦S < T ≦N.
• 1 ≦L ≦109.
• 1 ≦K ≦1015.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
• (Ai, Bi) , (Aj, Bj) (1 ≦i < j ≦M).
• 1 ≦Ci ≦109 (1 ≦i ≦M).
• 入力される値はすべて整数である.
- (8 点) L = 1,K = 2,Ci = 1 (1 ≦i ≦M).
- (16 点) N ≦50,M ≦50.
- (29 点) N ≦3 000,M ≦3 000.
- (47 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N M
S T L K
A1 B1 C1
A2 B2 C2
...
AM BM CM
標準出力に,国王が喜ぶような2 つの整数の選び方が何通りあるかを1 行で出力せよ.
第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)
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
4
3 2
1 3 1 2
1 2 1
2 3 1
3
6 4
2 5 1000000000 1
1 2 1000000000
2 3 1000000000
2 4 1000000000
5 6 1000000000
0
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
16