← 返回题目列表

AtCoder · joi2024ho_b

B. 建设项目2

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

配点: 100 点

問題文

在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 双向连接,其运动为 JOI国家将建设一条需要 L 分钟的铁路线。已经到站了 请注意,可能有一条铁路线在两个方向上连接 u 和车站 v 。

完成施工后,车站 S 从车站 T 使用多条铁路线 如果你能在 K 分钟内移动,国王会很高兴。请注意,不考虑铁路线的换乘时间和等待时间。

施工时 如何选择 2 整数 u, v 如何选择 \frac{N \left( N - 1 \right)}{2} 有很多选项,但你想知道有多少选项可以让国王满意。

当提供有关车站、铁路线和国王要求的信息时,我们将提供令国王满意的信息。 2 编写一个程序来查找选择两个整数的方法的数量。


入力

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

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

出力

标准输出包含一些令国王满意的内容。 2 选择两个整数有多少种方法? 1 行输出。


制約

  • 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).
  • 所有输入值都是整数。

小課題

  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 点)没有额外的限制。

入力例 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

出力例 1

4

例如,如果您 假设您选择 u = 3, v = 6 。车站 JOI 国家将建设一条需要 3 和车站 6 双向连接,其运动为 JOI国家将建设一条需要 1 分钟的铁路线。

此时,车站 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 满足约束。


入力例 2

3 2
1 3 1 2
1 2 1
2 3 1       

出力例 2

3

你怎么样 2 即使你选择一个整数,国王也会很高兴。换句话说,是让国王高兴的事情。 2 如何选择两个整数 3 方法有很多。因此,3 。 你只需要砍掉

此输入示例是一个小作业。 1,2,3,4 满足约束。


入力例 3

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

出力例 3

0

你怎么样 2 选择两个整数不会让国王满意。因此,0 。 你只需要砍掉

此输入示例是一个小作业。 2,3,4 满足约束。


入力例 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  

出力例 4

16

此输入示例是一个小作业。 2,3,4 满足约束。