#P1144. P1144 最短路计数

P1144 最短路计数

P1144 最短路计数

普及+/提高 | 来源:洛谷 | 原题链接

题意

给定 nn 个点、mm 条无向无权边(可能有自环与重边)。求 11 到每个点的最短路条数,对 100003100003 取模;无法到达输出 00。重边算不同的路(样例中 4→54\to5 有两条边,使方案数翻倍),自环不在任何最短路上。

输入格式

第一行包含 22 个正整数 N,MN,M,为图的顶点数与边数。

接下来 MM 行,每行 22 个正整数 x,yx,y,表示有一条连接顶点 xx 和顶点 yy 的边,请注意可能有自环与重边。

输出格式

共 NN 行,每行一个非负整数,第 ii 行输出从顶点 11 到顶点 ii 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 ans mod 100003 ans \bmod 100003 后的结果即可。如果无法到达顶点 ii 则输出 00。

输入输出样例

样例 1 输入

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例 1 输出

1
1
1
2
4

数据范围

1≤N≤1061\le N\le 10^6,1≤M≤2×1061\le M\le 2\times10^6;对 100003100003 取模。

提示

考点:BFS 分层 + 计数 DP:cnt[v] = Σ cnt[u](dist[u]+1=dist[v]dist[u]+1=dist[v] 的所有前驱)。易错点:① 重边有效(方案数×2)、自环无效(不在任何最短路上),都不需要特判——按层计数天然正确,但不要先对边去重;② 取模在累加时做;③ 11 号点答案是 11。

蜀ICP备2025119001号-1