分数: 700 点
问题陈述
我们有一个图表 N 顶点和 M 边,图上有两个人:高桥和青木。
的 i第一条边连接顶点 U_i 和顶点 V_i。 穿过这条边所需的时间是 D_i 分钟,无论方向和谁穿过边缘(高桥或青木)。
高桥离开顶点 S 和 Aoki 离开 Vertex T 同时。高桥前往 Vertex T 和青木前往顶点 S,都在最短的时间内完成。 求高桥和青木选择最短路径的方法对的数量,使他们在旅行过程中永远不会相遇(在顶点或边缘),模 10^9 + 7.
约束
- 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)
- If 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 是整数。
- 给定的图形已连接。
输入
输入由标准输入按以下格式给出:
N M S T U_1 V_1 D_1 U_2 V_2 D_2 : U_M V_M D_M
输出
打印答案。
示例输入 1
4 4 1 3 1 2 1 2 3 1 3 4 1 4 1 1
示例输出 1
2
有两种方法可以选择满足条件的最短路径:
- 高桥选择道路 1 \rightarrow 2 \rightarrow 3,青木选择路径 3 \rightarrow 4 \rightarrow 1.
- 高桥选择道路 1 \rightarrow 4 \rightarrow 3,青木选择路径 3 \rightarrow 2 \rightarrow 1.
示例输入 2
3 3 1 3 1 2 1 2 3 1 3 1 2
示例输出 2
2
示例输入 3
3 3 1 3 1 2 1 2 3 1 3 1 2
示例输出 3
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
示例输出 4
6