题目:
https://www.luogu.com.cn/problem/P1144
用bfs来求最短路,用dep数组来表示深度,用c数组来表示从1到达当前状态的数量
如果当前的dep[w]==dep[te]+1的话就把到达te的次数加给w
代码:
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int maxn=1e6+6; const int maxm=2e6+6; const int mod=100003; vector<int> G[maxn]; int n,m; int v[maxn],c[maxn],dep[maxn]; int main() {scanf("%d %d",&n,&m); int x,y; for(int i=1;i<=m;i++) { scanf("%d %d",&x,&y); G[x].push_back(y); G[y].push_back(x); } queue<int> q; q.push(1); v[1]=1; dep[1]=0; c[1]=1; while(!q.empty()) { int te=q.front(); q.pop(); for(int j=0;j<G[te].size();j++) { int w=G[te][j]; if(!v[w]) { v[w]=1; dep[w]=dep[te]+1; q.push(w); } if( dep[w]==dep[te]+1) { c[w]=(c[w]+c[te])%mod; //来源只能是depth比他小一的数 // printf("w=%d te=%d\n",w,te); // printf("c[w]=%d c[te]=%d\n",c[w],c[te]); } } } for(int i=1;i<=n;i++) printf("%d\n",c[i]); }