AT_joi2024ho_b 建設事業 2 (Construction Project 2)

JOI 国有 $N$ 个火车站，编号为 $1$ 到 $N$。此外，JOI 国有 $M$ 条铁路线，编号为 $1$ 到 $M$。第 $i$ 条铁路线（$1 \leq i \leq M$）连接车站 $A_i$ 和车站 $B_i$（为双向通行），通过该线路需要 $C_i$ 分钟。 作为 JOI 国的大臣，你将新增 $1$ 条铁路线，其方式如下： - 选择满足 $1 \leq u < v \leq N$ 的整数 $u, v$。修建一条连接车站 $u$ 和车站 $v$ 的双向铁路线，通过该线路需要 $L$ 分钟。注意，即使 $u$ 和 $v$ 之间已经存在铁路线，也可以再建。 - 修建完成后，如果可以从车站 $S$ 出发，经若干铁路线，在 $K$ 分钟以内到达车站 $T$，国王就会感到高兴。不考虑换乘时间和候车时间。 所有可能的整数对 $(u, v)$ 共有 $\frac{N (N-1)}{2}$ 种。你的任务是求出，在所有这些选择中，能够让国王感到高兴的 $(u, v)$ 的方案数。 给定火车站与铁路线、以及国王的期望，请编写程序，计算能让国王高兴的整数对有多少种。

输入通过标准输入给出，格式如下： > $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$

输出一行，表示能让国王高兴的整数对的方案数。

## 小子任务 1. （$8$ 分）$L = 1$，$K = 2$，$C_i = 1$（$1 \leq i \leq M$）。 2. （$16$ 分）$N \leq 50$，$M \leq 50$。 3. （$29$ 分）$N \leq 3000$，$M \leq 3000$。 4. （$47$ 分）无额外约束。 ## 样例解释 1 比如选择 $u = 3, v = 6$，即修建一条连接车站 $3$ 和车站 $6$，耗时 $1$ 分钟的铁路线。 此时，可以从 $6$ 号站经这条新线路到 $3$ 号站，再从 $3$ 号站经已有铁路到 $7$ 号站，整个过程共需 $2$ 分钟。这样就能在 $2$ 分钟内到达 $7$ 号站，所以国王高兴。 国王高兴的整数对，包括上述情况，共有 $4$ 种。因此输出 $4$。 此输入满足小子任务 $1,2,3,4$ 的约束。 ## 样例解释 2 不论选哪一组整数对，国王都高兴，因此方案数为 $3$，输出 $3$。 此输入满足小子任务 $1,2,3,4$ 的约束。 ## 样例解释 3 不论选哪一组整数对，国王都不会高兴，因此输出 $0$。 此输入满足小子任务 $2,3,4$ 的约束。 ## 样例解释 4 此输入满足小子任务 $2,3,4$ 的约束。 # 数据范围 - $2 \leq N \leq 200\,000$。 - $1 \leq M \leq 200\,000$。 - $1 \leq S < T \leq N$。 - $1 \leq L \leq 10^9$。 - $1 \leq K \leq 10^{15}$。 - $1 \leq A_i < B_i \leq N$（$1 \leq i \leq M$）。 - $(A_i, B_i) \neq (A_j, B_j)$（$1 \leq i < j \leq M$）。 - $1 \leq C_i \leq 10^9$（$1 \leq i \leq M$）。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译