题目详情题解（0）讨论（0）提交记录（0）

AT_arc090_c.[ARC090E] Avoiding Collision

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

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

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

输入格式

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

NN MM SS TT
U1U_1 V1V_1 D1D_1
U2U_2 V2V_2 D2D_2
⋮\vdots
UMU_M VMV_M DMD_M

输出格式

请输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    2

  • 输入#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

说明/提示

限制条件

  • 1≤N≤100,0001 \leq N \leq 100,000
  • 1≤M≤200,0001 \leq M \leq 200,000
  • 1≤S,T≤N1 \leq S, T \leq N
  • S≠TS \neq T
  • 1≤Ui,Vi≤N1 \leq U_i, V_i \leq N（1≤i≤M1 \leq i \leq M）
  • 1≤Di≤1091 \leq D_i \leq 10^9（1≤i≤M1 \leq i \leq M）
  • 当 i≠ji \neq j 时，(Ui,Vi)≠(Uj,Vj)(U_i, V_i) \neq (U_j, V_j) 且 (Ui,Vi)≠(Vj,Uj)(U_i, V_i) \neq (V_j, U_j)
  • Ui≠ViU_i \neq V_i（1≤i≤M1 \leq i \leq M）
  • DiD_i 是整数
  • 给定的图保证是连通的

样例说明 1

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

  • 高桥君走 1→2→31 \rightarrow 2 \rightarrow 3，青木君走 3→4→13 \rightarrow 4 \rightarrow 1。
  • 高桥君走 1→4→31 \rightarrow 4 \rightarrow 3，青木君走 3→2→13 \rightarrow 2 \rightarrow 1。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页