题目描述

难度分:$2100$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$，表示一个$n$点$m$边的无向图。

然后输入$s$和$t(s \neq t)$，表示起点和终点。节点编号从$1$开始。

然后输入$m$条边，每条边输入$x$、$y$，表示有一条无向边连接$x$和$y$。

保证图是连通的。保证图中无自环和重边。

设从$s$到$t$的最短路长度为$d$。输出从$s$到$t$的路径个数，要求路径的长度至多为$d+1$。答案模$10^9+7$。

输入样例

4


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


6 8
6 1
1 4
1 6
1 5
1 2
5 6
4 6
6 3
2 6


5 6
1 3
3 5
5 4
3 1
4 2
2 1
1 4


8 18
5 1
2 1
3 1
4 2
5 2
6 5
7 3
8 4
6 4
8 7
1 4
4 7
1 6
6 7
3 8
8 5
4 5
4 3
8 2

输出样例

2
4
1
11

算法

BFS+前后缀分解

比较容易想到要从起点$s$和终点$t$分别进行BFS，然后枚举一个中间节点$i$做前后缀分解，组合前面的方案（从$s$到$i$的路径）和后面的方案（从$i$到$t$的路径）。但是有一些细节要处理一下，在做BFS的过程中我们其实就可以通过DP来计数。

动态规划

状态定义

$f[i]$表示从起点到$i$是最短路的方案数。

状态转移

当遍历到某个节点$u$时，展开它的所有邻居$v$：

1. 如果$dist[v] \lt dist[u]+1$，更新最短路，扩展队列。
2. 如果$dist[v]=dist[u]+1$，说明此时的最短路是不变的，直接把起点到$u$的方案数$f[u]$累加到$f[v]$上，也就是说有多少条到$u$的最短路就有多少条到$v$的最短路。

但我们做完BFS之后还只是求得了最短路的方案数，如果以$s$为起点做BFS得到的DP数组为$fs$，把答案初始化为$fs[t]$，这就是从$s$到$t$距离为最短路$d$时的所有方案数。

然后我们直接考虑距离为$d+1$时的情况，假设以$s$为起点得到的$dist$数组为$ds$，DP数组为$fs$，以$t$为起点得到的$dist$数组为$dt$，DP数组为$ft$。枚举一个中间节点$i$，我们希望这时候从$s$经过$i$到$t$时的距离为$d+1$，说明要多经过一条边到$j$，然后$j$继续走最短路，可以枚举$i$的邻居$j$。

此时需要满足以下两个条件：

1. $ds[i]+dt[j]=d$，这样算上$i$到$j$这条边就能得到$d+1$这个距离。
2. $ds[i]=ds[j]$，这就说明从$s$到$j$的最短路根本就没必要经过$i$，$i$到$j$这条边根本就是强行加上去的。

把所有满足这两个条件的$fs[i] \times ft[j]$累加起来就是距离为$d+1$时的路径数，算上前面距离为$d$时的路径数就是最终答案。

复杂度分析

时间复杂度

跑两遍BFS求$s$和$t$到各点的最短路，在遍历的过程中利用DP统计，时间复杂度为$O(n+m)$。然后遍历中间点$i$及其邻居$j$，在最差情况下其实就是遍历所有节点和边，时间复杂度仍然是$O(n+m)$。因此，整个算法的时间复杂度为$O(n+m)$。

空间复杂度

图的邻接表空间消耗为$O(n+m)$，BFS求最短路时的$dist$数组和DP数组$f$的空间都是线性的，为$O(n)$。因此，整个算法的额外空间复杂度为$O(n+m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int T, n, m;
vector<int> graph[N];

pair<vector<int>, vector<int>> bfs(int src) {
    vector<int> dist(n + 1, INF);
    queue<int> q;
    q.push(src);
    dist[src] = 0;
    vector<int> f(n + 1);
    f[src] = 1;
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nxt: graph[cur]) {
            if(dist[nxt] == INF) {
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
            if(dist[nxt] == dist[cur] + 1) {
                f[nxt] = (f[nxt] + f[cur]) % MOD;
            }
        }
    }
    return make_pair(dist, f);
}

void solve() {
    scanf("%d%d", &n, &m);
    int s, t;
    scanf("%d%d", &s, &t);
    for(int i = 1; i <= n; i++) {
        graph[i].clear();
    }
    for(int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    auto [ds, fs] = bfs(s);
    auto [dt, ft] = bfs(t);
    int d = ds[t], ans = fs[t];
    for(int i = 1; i <= n; i++) {
        for(int j: graph[i]) {
            if(ds[i] + dt[j] == d && ds[i] == ds[j]) {
                ans = (ans + (LL)fs[i] * ft[j] % MOD) % MOD;
            }
        }
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        solve();
    }
    return 0;
}