题目链接：https://www.luogu.com.cn/problem/P1144

求到达每个点的最短路个数，从层次出发，采用bfs进行每一次搜索，通过vis控制回路问题
题目数据范围较大，采用动态建图

借鉴dalao代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=1000000+1,maxm=2000000+1,INF=0x7f7f7f7f,MOD=100003;
vector<int>G[maxn];int dep[maxn];bool vis[maxn];int cnt[maxn];

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);//比邻接矩阵那种省空间
    }
    queue<int>Q;dep[1]=0;vis[1]=1;Q.push(1);cnt[1]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0;i<G[x].size();i++){
            int t=G[x][i];//取出x访问到的点 
            if(!vis[t]){vis[t]=1;dep[t]=dep[x]+1;Q.push(t);}
			//如果到t的深度为到x的深度+1,那么将到t的原有数量再加上到x可走的数量，有亿点儿难 
            if(dep[t]==dep[x]+1)	{cnt[t]=(cnt[t]+cnt[x])%MOD;}
        }
    }
    for(int i=1;i<=N;i++){
        printf("%d\n",cnt[i]);
    }
    return 0;
}