/* 边权值都为1,所以可以用BFS来做 记住 BFS 和 dikstra 都是满足拓扑序性质的,也就是说可以用二者解决图论中的dp问题,而spfa不满足拓扑序的性质 */ #include<bits/stdc++.h> using namespace std; const int N=1e6+10,M=4e6+10,P=100003; int n,m; int h[N],e[M],ne[M],idx; int cnt[N],dis[N]; bool st[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } /* 其实st数组是不需要的,因为bfs中每个点第一次入队时的距离是最小的,而我们初始化dis为正无穷,所以如果dis[j]<dis[t]+1,即如果j能被t这个点更新,说明j这个点还没有入过队 */ /* if(dis[j]>dis[t]+1)//第一次被遍历 { dis[j]=dis[t]+1; cnt[j]=cnt[t]; q.push(j); } else if(dis[j]==dis[t]+1)//被与遍历这个点的同一层的其他点遍历 cnt[j]=(cnt[j]+cnt[t])%P; */ void bfs() { memset(dis,0x3f,sizeof dis); queue<int> q; dis[1]=0,cnt[1]=1; st[1]=true; q.push(1); while(q.size()) { int t=q.front(); q.pop(); for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dis[j]==dis[t]+1)//不是第一次遍历了 cnt[j]=(cnt[j]+cnt[t])%P; if(st[j]) continue; st[j]=true; //第一次被遍历 dis[j]=dis[t]+1; cnt[j]=cnt[t]; q.push(j); } } } int main() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); while(m--) { int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } bfs(); for(int i=1;i<=n;i++) printf("%d\n",cnt[i]); return 0; }
标签:cnt,遍历,idx,int,短路,st,计数,dis From: https://www.cnblogs.com/tolter/p/17212472.html