题解 P1144 【最短路计数】

- 本来写了个和一些题解比较相像的什么$SPFA$、$Dijkstra$之类的，后面出$bug$懒得弄了，就看了眼题解，第一篇$dalao$用$bfs$做，做法十分清爽，不得不orz。但是为什么很多$dalao$写的题解都比较简略呢。。。。看来我太菜了吧QAQ - 所以我就写了一篇$dalao$代码较详细的解释。因为边的权值都为1，所以这道题才能用$bfs$，$dalao$说的： > 一个点最短路一定经过了一个层数比它少一的结点（否则不是最短路）。 > > 所以用每个相邻且层数比当前结点层数少一的点更新当前点的路径跳数即可。 有一些人看不懂，这中间的层数就是离源点（顶点1）的距离，或者说是$bfs$搜索树的深度。所以这个最短路一定是沿着从深度比它少1的结点来的，不然它就不算最短路，这个跳数应该就是把最短路数量从旁边的点转移过来。 - Code：更多解释请看代码 ```cpp #include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #define INF 1<<30 #define Mod 100003 using namespace std; vector<int> G[1000005];//注意这是2维数组，用来存每一个点所连的边，而题目中有10^6个点，所以是10^6+5 queue<int>Q;//bfs所需要的队列 int dep[1000005],cnt[1000005];//dep是每个点对于源点的深度，cnt储存答案，即到点i的最短路个数 bool vis[1000005];//判断点是否使用 int main(){ int N,M; scanf("%d%d",&N,&M); for(int i=1;i<=M;i++){ int x,y;scanf("%d%d",&x,&y); G[x].push_back(y);//存边，无向图存有向边两次 G[y].push_back(x); } dep[1]=0; vis[1]=1; Q.push(1); cnt[1]=1; while(!Q.empty()){//bfs核心代码 int x=Q.front(); Q.pop(); for(int i=0;i<G[x].size();i++){//遍历点所连的每一条边 int t=G[x][i]; if(!vis[t]){ vis[t]=1; dep[t]=dep[x]+1;//深度+1 Q.push(t); } if(dep[t]==dep[x]+1)//dalao说的最后一句话，这个点直接从旁边深度-1的结点添加最短路数量 cnt[t]=(cnt[t]+cnt[x])%Mod;//不要忘记要%Mod } } for(int i=1;i<=N;i++) printf("%d\n",cnt[i]); return 0; } ``` - %%%[GGN_2015](https://www.luogu.org/space/show?uid=36456) - 本人个人[Blog](https://www.17shou.vip/)，欢迎$dalao$进来拍砖，交换友链什么的^ _ ^