#P1144. P1144 最短路计数
P1144 最短路计数
P1144 最短路计数
普及+/提高 | 来源:洛谷 | 原题链接
题意
给定 个点、 条无向无权边(可能有自环与重边)。求 到每个点的最短路条数,对 取模;无法到达输出 。重边算不同的路(样例中 有两条边,使方案数翻倍),自环不在任何最短路上。
输入格式
第一行包含 个正整数 ,为图的顶点数与边数。
接下来 行,每行 个正整数 ,表示有一条连接顶点 和顶点 的边,请注意可能有自环与重边。
输出格式
共 行,每行一个非负整数,第 行输出从顶点 到顶点 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 后的结果即可。如果无法到达顶点 则输出 。
输入输出样例
样例 1 输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
样例 1 输出
1
1
1
2
4
数据范围
,;对 取模。
提示
考点:BFS 分层 + 计数 DP:cnt[v] = Σ cnt[u]( 的所有前驱)。易错点:① 重边有效(方案数×2)、自环无效(不在任何最短路上),都不需要特判——按层计数天然正确,但不要先对边去重;② 取模在累加时做;③ 号点答案是 。