P1144 最短路计数

对于100%的数据，N<=1000000,M<=2000000。

但是我 只开 4e5 就 跑过了。

不知道是 数据太水 还是 题描述有误 。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a,b;
int fir[400005],nxt[400005],to[400005],top=0;
int dl[100005],l=1,r=0;
int js[100005];
int jr;
int pd[100005];
void add(int x,int y){
	top++;nxt[top]=fir[x];fir[x]=top;to[top]=y;
}
void bfs(){
	dl[++r]=1;
	js[1]=1;
	pd[1]=1;
	while(l<=r){
		jr=r;
		for(int i=l;i<=jr;i++){
			pd[dl[i]]=1;
		}
		for(int i=l;i<=jr;i++){
			js[dl[i]]%=100003;
			for(int j=fir[dl[i]];j;j=nxt[j]){
				if(pd[to[j]]==0){
					if(js[to[j]]==0)dl[++r]=to[j];

					js[to[j]]+=js[dl[i]];
				}
			}
		}
		l=jr+1;
		}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		add(a,b);
		add(b,a);
	}
	memset(js,0,sizeof(js));
	memset(pd,0,sizeof(pd));
	bfs();
	for(int i=1;i<=n;i++){
		cout<<js[i]<<endl;
	}
	return 0;
}