A - 2540
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の駅があり、M 本の線路で結ばれています。
線路 i は駅 A_i と駅 B_i を直接結んでおり、路線長は L_i mです。
a < c,a \neq b,b \neq c を満たす (a,b,c) の組で、駅 a と駅 b の間、駅 b と駅 c の間を直接結ぶ線路が存在し、かつ 2 つの路線長の和が 2540 mとなるものがいくつあるか求めてください。
同じ駅どうしを結ぶ路線や、線路の通らない駅が存在しないことは保証されますが、全ての駅が連結とは限りません。
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i < B_i \leq N
- (A_i,B_i) \neq (A_j,B_j) (i \neq j)
- 1000 \leq L_i \leq 2000
- 入力は全て整数
- 線路の通らない駅は存在しない
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 L_1 : A_M B_M L_M
出力
条件を満たす (a,b,c) の組が x 通りあるとき、x を出力せよ。
入力例 1
4 3 1 2 1420 2 3 1120 3 4 1420
出力例 1
2
(1,2,3),(2,3,4) が条件を満たします。
入力例 2
4 2 1 2 1920 3 4 1125
出力例 2
0