问题描述：

N个顶点M条边的无向无权图，顶点编号为1−N。问从顶点1开始，到其他每个点的最短路有几条。

 

概念：

我们可以找出一个图的最短路，这张图有不同路径满足这个路径最短的限制。求不同路径数量称为最短路计数。

 

思路：

在跑最短路的时候用Cnt数组记录最短路条数。（Dij和SPFA都能搞）

在松弛每个点时，更新完最短路后判断是否满足dis[to]=dis[fr]+1，意思就是to这个点的最短路是否可以由fr更新。

根据加法原理，将Cnt[fr]加到Cnt[to]里。

这样就正确处理了Cnt数组，也就解决了问题。