算法
(BFS树、DAG上DP) $O(N + M)$
其中绿色数字表示起点到当前点的最短路的距离,蓝色数字表示 BFS树
的层号
由上图我们可以观察到,起点到当前点的最短路必然不可能由同一层的节点转移过来,而只会由上一层的点转移过来,这样就能保证最短,这就是 BFS树
的天然的漂亮性质。
于是本题就变成了 $\rm DAG$ 上最短路计数问题,然后我们很自然的就联想到 $\rm DP$。
记 $dp[v]$ 表示起点到当前点的最短路的数量,然后由上一层和点 $v$ 有直接相连的点的 $dp$ 值来更新它。
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
using mint = modint1000000007;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
const int INF = 1001001001;
vector<int> dist(n, INF);
queue<int> q;
q.push(0); dist[0] = 0;
vector<int> vs;
while (q.size()) {
int v = q.front(); q.pop();
vs.push_back(v);
for (int u : to[v]) {
if (dist[u] != INF) continue;
dist[u] = dist[v] + 1;
q.push(u);
}
}
vector<mint> dp(n);
dp[0] = 1;
for (int v : vs) {
for (int u : to[v]) {
if (dist[u] == dist[v] + 1) {
dp[u] += dp[v];
}
}
}
mint ans = dp[n - 1];
cout << ans.val() << '\n';
return 0;
}
211场 是dp专场吧。。。。
!代码比他们简洁多了