不知道为什么会输出0
#include <iostream>
#include <cstdio>
using namespace std;
int dl[2000001]={};//bfs队列
struct las//每个点最短路的结构体
{
int duan;//最短路长度
int num;//个数
}zd[1000001];//数组
struct bia//邻接表存边
{
int from;
int to;
int nex;
bool use=false;
}bian[2000001];
struct hed
{
int fir;
int las;
int num;
}head[1000001];
int p=0;
void lian(int a,int b)//连边
{
p++;
if(head[a].num)
{
bian[head[a].las].nex=p;
head[a].las=p;
head[a].num++;
bian[p].from=a;
bian[p].to=b;
}
else
{
head[a].fir=head[a].las=p;
head[a].num=1;
bian[p].from=a;
bian[p].to=b;
}
}
int main()
{
//数据读入与处理
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
if(a==b)
continue;
lian(a,b);
lian(b,a);
}
int hd=1;
int tl=2;
dl[1]=1;//队列1为开头
zd[1].duan=0;
zd[1].num=1;//1的最短路是0,只有1种
//bfs
while(tl>hd)//bfs
{
for(int i=head[hd].fir;i;i=bian[i].nex)
{
if((zd[bian[i].to].duan!=0&&zd[bian[i].to].duan<=zd[bian[i].from].duan)||bian[i].to==1)//如果最短路被更新了并且现在的深度比最短路大,或这条边指向1,continue
continue;
else
{
// printf("%d %d %d\n",dl[hd],bian[i].to,bian[i].from);
zd[bian[i].to].duan=zd[bian[i].from].duan+1;//最短路长度(bfs第一次进搜索树就是最短路)
zd[bian[i].to].num+=zd[bian[i].from].num;//最短路个数
zd[bian[i].to].num%=100003;
dl[tl]=bian[i].to;//队列设置
tl++;
}
}
hd++;
}
for(int i=1;i<=n;i++)
{
printf("%d\n",zd[i].num);
}//输出
return 0;
}