BFS 分层并在最短层边上累加方案数，支持重边。
OJ: luogu
题目 ID: P1144
难度:普及+/提高-
标签:BFS最短路计数前向星python
日期: 2026-07-17 03:00
题意
无向无权图中，统计 1 到每个点的最短路径条数。
思路
BFS 首次访问确定最短距离。对边 u-v，若 dist[v]=dist[u]+1，所有到 u 的最短路都能扩展成到 v 的最短路；重边会被分别遍历，正好分别计数。
Python 知识
- 百万点、两百万边用
array前向星控制内存。 array加游标模拟队列，避免大量 deque 整数对象。- 输出按 8192 行分块，控制字符串峰值内存。
代码
python
import sys
from array import array
input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
head = array("i", [-1]) * (n + 1)
to = array("i", [0]) * (2 * edges)
next_edge = array("i", [0]) * (2 * edges)
edge_count = 0
def add_edge(u, v):
global edge_count
to[edge_count] = v
next_edge[edge_count] = head[u]
head[u] = edge_count
edge_count += 1
for _ in range(edges):
u, v = map(int, input().split())
add_edge(u, v)
add_edge(v, u)
distance = array("i", [-1]) * (n + 1)
ways = array("i", [0]) * (n + 1)
distance[1] = 0
ways[1] = 1
queue = array("i", [1])
index = 0
while index < len(queue):
node = queue[index]
index += 1
edge = head[node]
while edge != -1:
neighbor = to[edge]
if distance[neighbor] == -1:
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
if distance[neighbor] == distance[node] + 1:
ways[neighbor] = (ways[neighbor] + ways[node]) % 100003
edge = next_edge[edge]
output = sys.stdout.write
buffer = []
for node in range(1, n + 1):
buffer.append(str(ways[node]))
if len(buffer) == 8192:
output("\n".join(buffer) + "\n")
buffer.clear()
output("\n".join(buffer))原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXM = 2000005;
const int MOD = 100003;
int n, m;
int head[MAXN], to[MAXM * 2], nxt[MAXM * 2], edge_cnt;
int dist_node[MAXN];
int ways[MAXN];
void add_edge(int u, int v) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
}
void bfs() {
for (int i = 1; i <= n; i++) {
dist_node[i] = -1;
ways[i] = 0;
}
queue<int> que;
dist_node[1] = 0;
ways[1] = 1;
que.push(1);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (dist_node[v] == -1) {
dist_node[v] = dist_node[u] + 1;
ways[v] = ways[u];
que.push(v);
} else if (dist_node[v] == dist_node[u] + 1) {
ways[v] += ways[u];
if (ways[v] >= MOD) {
ways[v] %= MOD;
}
}
}
}
}
void solve() {
bfs();
for (int i = 1; i <= n; i++) {
cout << ways[i] % MOD << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
时间 O(n+m)，空间 O(n+m)。
总结
无权最短路计数只在相邻 BFS 层之间累加方案。