AT_arc090_c [ARC090E] Avoiding Collision

题目描述

有一个包含 $N$ 个顶点和 $M$ 条边的图，在这张图上有高桥君和青木君。

第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。无论是谁（高桥君或青木君）通过，也无论通过方向如何，通过这条边所需的时间都是 $D_i$ 分钟。

高桥君从顶点 $S$ 出发，青木君从顶点 $T$ 出发，他们同时开始，分别以最短时间从自己的起点移动到终点（高桥君的终点为 $T$，青木君的终点为 $S$）。请计算在不经过途中相遇（即两人不在同一条边或者顶点相遇）的前提下，最短路的选择方案有多少种，将答案对 $10^9+7$ 取模后输出。

输入格式

输入以如下格式从标准输入读入：

$N$ $M$ $S$ $T$
$U_1$ $V_1$ $D_1$
$U_2$ $V_2$ $D_2$
$\vdots$
$U_M$ $V_M$ $D_M$

输出格式

请输出答案。

样例 1

输入

4 4
1 3
1 2 1
2 3 1
3 4 1
4 1 1

输出

2

样例 2

输入

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

输出

2

样例 3

输入

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

输出

2

样例 4

输入

8 13
4 2
7 3 9
6 2 3
1 6 4
7 6 9
3 8 9
1 2 2
2 8 12
8 6 9
2 5 5
4 2 18
5 3 7
5 1 515371567
4 8 6

输出

6

说明/提示

限制条件

• $1 \leq N \leq 100,000$
• $1 \leq M \leq 200,000$
• $1 \leq S, T \leq N$
• $S \neq T$
• $1 \leq U_i, V_i \leq N$（$1 \leq i \leq M$）
• $1 \leq D_i \leq 10^9$（$1 \leq i \leq M$）
• 当 $i \neq j$ 时，$(U_i, V_i) \neq (U_j, V_j)$ 且 $(U_i, V_i) \neq (V_j, U_j)$
• $U_i \neq V_i$（$1 \leq i \leq M$）
• $D_i$ 是整数
• 给定的图保证是连通的

样例说明 1

满足条件的最短路选择有以下两种：

• 高桥君走 $1 \rightarrow 2 \rightarrow 3$，青木君走 $3 \rightarrow 4 \rightarrow 1$。
• 高桥君走 $1 \rightarrow 4 \rightarrow 3$，青木君走 $3 \rightarrow 2 \rightarrow 1$。

由 ChatGPT 5 翻译