← 返回题目列表

AtCoder · arc090_c

E. 避免碰撞

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

分数: 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