题目

为神马样例最后一个输出2

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010,M=4000010;
const int mod=100003;
int n,m,x,y,num;
int head[N],nxt[M],to[M],dis[N],ans[N];
bool vis[N];
struct node{
	int num,dis;
	bool operator < (const node &a)const{
		return dis<a.dis;
	}
};
priority_queue<node>q;
void add(int a,int b){
	to[++num]=b;
	nxt[num]=head[a];
	head[a]=num;
}
void dij(){
	for(int i=1;i<=n;i++){
		dis[i]=1e9;
	}
	node t;
	ans[1]=1;
	dis[1]=0;
	t.dis=0;
	t.num=1;
	q.push(t);
	while(!q.empty()){
		x=q.top().num;
		q.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=true;
		for(int i=head[x];i;i=nxt[i]){
			y=to[i];
			if(dis[y]>dis[x]+1){
				ans[y]=ans[x];
				dis[y]=dis[x]+1;
				t.num=y;
				t.dis=dis[y];
				q.push(t);
			}
			else if(dis[y]==dis[x]+1){
				ans[y]+=ans[x];
				ans[y]%=mod;
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dij();
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	} 
	return 0;
}