【Luogu】P1144最短路计数（BFS）
题目链接
此题使用BFS记录最短路的条数。思路如下：
因为是无权无向图，所以只要被BFS到就是最短路径。因此可以记录该点的最短路和最短路的条数：
如果点y还没被访问过，则记录dis[y],同时令ans[y]=ans[x]. 如果点y已经被访问过且当前为最短路径，则ans[y]+=ans[x]
#include<cstdio> #include<cctype> inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } struct Edge{ int next,to; }edge[4000010]; int head[1000010],num; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } int f[2000000],h,t=1; int dis[1000010]={-1},ans[1000010]={0,1}; int main(){ int n=read(),m=read(); for(int i=1;i<=m;++i){ int from=read(),to=read(); if(from==to) continue; add(from,to); add(to,from); } f[1]=1; while(h++<t) for(int i=head[f[h]];i;i=edge[i].next) if(!dis[edge[i].to]&&edge[i].to!=1){ dis[edge[i].to]=dis[f[h]]+1; f[++t]=edge[i].to; ans[edge[i].to]=ans[f[h]]; } else if(dis[edge[i].to]==dis[f[h]]+1) ans[edge[i].to]=(ans[edge[i].to]+ans[f[h]])%100003; for(int i=1;i<=n;++i) printf("%d ",ans[i]); }