CF1650G Counting Shortcuts

给定一个无向连通图，包含 $n$ 个顶点和 $m$ 条边。图中不包含自环（即不存在从某个顶点到自身的边）和重边（即任意一对顶点之间至多只有一条边）。顶点编号为 $1$ 到 $n$。 请你计算，从顶点 $s$ 到顶点 $t$ 的所有路径中，长度与 $s$ 到 $t$ 的最短路径长度之差不超过 $1$ 的路径数。需要统计所有满足条件的路径，即使这些路径经过同一个顶点或边多次（即路径不要求简单路径）。  例如，设 $n=6$，$m=8$，$s=6$，$t=1$，图如上图所示。那么 $s$ 到 $t$ 的最短路径长度为 $1$。考虑所有长度不超过 $1+1=2$ 的路径： - $6 \rightarrow 1$，路径长度为 $1$。 - $6 \rightarrow 4 \rightarrow 1$，路径长度为 $2$。 - $6 \rightarrow 2 \rightarrow 1$，路径长度为 $2$。 - $6 \rightarrow 5 \rightarrow 1$，路径长度为 $2$。 一共有 $4$ 条满足条件的路径。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例前有一个空行。 每个测试用例的第一行包含两个整数 $n, m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$），分别表示图的顶点数和边数。 第二行包含两个整数 $s$ 和 $t$（$1 \le s, t \le n$，$s \neq t$），分别表示路径的起点和终点。 接下来的 $m$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$），表示第 $i$ 条边连接的两个顶点。 保证图是连通的，且不包含自环和重边。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，$m$ 的总和也不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示从 $s$ 到 $t$ 的所有路径中，长度与最短路径长度之差不超过 $1$ 的路径数。由于答案可能很大，请对 $10^9+7$ 取模后输出。

由 ChatGPT 4.1 翻译