洛谷 P1144 最短路计数(bfs模板题,稍加修改)
题目链接:最短路计数 - 洛谷https://www.luogu.com.cn/problem/P1144思路:基本上是一个模板题,只不过要输出的不是最短路距离,而是最短路数量,所以需要一个cnt数组,如果当前是更短的最短路,cnt重新计数,等于到上个点的cnt值,如果当前是和之前长度相等的最短路,cnt和之前累加。注意答案取模。当时做这道题没有什么感觉,套完模板稀里糊涂的就ac了,写完之后总结了一下感觉收获不少。最短路问题中,dist数组和vis数组是必不可少的,dist数组用来记录最短.