Acwing1134

算法讲解：短路求方案数问题

问题描述

给定一个无向图，求从起点 $1$ 到每个节点的最短路径的方案数（即有多少条不同的路径可以到达该节点，且路径长度是最短的）。

关键点

拓扑性：
- 只有 BFS 和 Dijkstra 算法天然具备拓扑性（每次扩展节点时，路径一定是当前最短的）。
- SPFA 不具备这种特性，因为队列中可能会重复处理某些节点，打破路径的拓扑顺序，导致结果错误。
核心思想：
- 在判断 dist[j] = dist[t] + w[i] 时，累计当前方案数。
- 如果发现另一条到达同样距离的路径，继续累加方案数。

代码解析

1. 数据结构定义

const int N = 100010, M = 400010, mod = 100003;int n, m;
int h[N], e[M], ne[M], idx; // 邻接表存储图
int dist[N], cnt[N]; // 最短路径距离 & 方案数

邻接表：
- h[u]：节点 $u$ 的第一条边的索引。
- e[idx]、ne[idx]：链式前向星存储目标节点和下一条边的索引。
路径属性：
- dist[u]：从起点 $1$ 到节点 $u$ 的最短路径长度。
- cnt[u]：从起点 $1$ 到节点 $u$ 的最短路径方案数。

2. 添加边

void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

使用链式前向星添加边。
因为是无向图，每次输入需要调用两次 add，构建双向边。

3. BFS 算法

void bfs() {queue<int> q;q.push(1); // 从起点开始搜索memset(dist, 0x3f, sizeof dist); // 初始化所有点的距离为无穷大dist[1] = 0; // 起点的最短路径为 0cnt[1] = 1; // 起点的方案数为 1while (q.size()) {int t = q.front(); // 当前节点q.pop();for (int i = h[t]; ~i; i = ne[i]) { // 遍历当前节点的所有邻边int j = e[i]; // 目标节点if (dist[j] > dist[t] + 1) { // 找到更短路径dist[j] = dist[t] + 1; // 更新距离cnt[j] = cnt[t]; // 继承当前方案数q.push(j); // 入队} else if (dist[j] == dist[t] + 1) { // 找到同样短的路径cnt[j] = (cnt[j] + cnt[t]) % mod; // 累加方案数并取模}}}
}

关键点解析

初始化：
- 起点的 dist[1] = 0，cnt[1] = 1，表示从起点到起点只有一种方案。
- 其他节点的 dist 初始化为无穷大，cnt 初始化为 0。
松弛操作：
- 如果发现更短路径 dist[j] > dist[t] + 1：
  - 更新目标节点的最短距离。
  - 当前节点的方案数继承给目标节点。
- 如果发现同样短的路径 dist[j] == dist[t] + 1：
  - 累加当前节点的方案数。
拓扑性：
- BFS 确保了路径的拓扑顺序，先处理距离较短的节点。
- 因此，每次更新 cnt[j] 时，已经保证了当前路径是最短路径。

4. 主函数

int main() {cin >> n >> m;memset(h, -1, sizeof h); // 初始化邻接表while (m--) {int a, b;cin >> a >> b;add(a, b), add(b, a); // 添加双向边}bfs();for (int i = 1; i <= n; i++) cout << cnt[i] << endl; // 输出每个点的方案数return 0;
}