本蒟蒻也来发一次题解第一篇请见谅

这个题有几个要点

1.无向无权图，建图的时候别忘记建来回的有向边【因此WA掉1次

2.无权嘛，那么边长建成1就好了2333333

3.最短路采用迪杰斯特拉（别忘用堆优化）来做，计数操作改装进去，ans[1]=1;迪杰斯特拉更新边长的时候如果大于号（具体见代码）就覆盖，相等的话就加上

4.%楼上SPFA，BFS大佬

具体见代码，其实就是在迪杰斯特拉里面填了几笔（逃

代码巨丑（捂脸）

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 1000006

using namespace std;

int n,m,s=1;

int dis[maxn];

int ans[maxn];

struct Edge{

    int t,nxt,w;

}edge[maxn*4];

int book[maxn];

int head[maxn],tot=0;

priority_queue< pair<int,int> > hep;

void add(int st,int to,int we){

    edge[tot].t=to;

    edge[tot].nxt=head[st];

    edge[tot].w=we;

    head[st]=tot;

    tot++;

}

void init(){

    scanf("%d %d",&n,&m);

    memset(book,0,sizeof(book));

    memset(head,-1,sizeof(head));

    memset(dis,0x3f,sizeof(dis));

    memset(ans,0,sizeof(ans));

    for(int i=1;i<=m;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        add(a,b,1);

        add(b,a,1);

    }

    dis[s]=0;

    ans[s]=1;

    return;

}

void dij(){

    hep.push(make_pair(0-dis[s],s));

    while(!hep.empty()){

        int np=hep.top().second;hep.pop();

        if(book[np]) continue;

        book[np]=1;

        for(int i=head[np];i!=-1;i=edge[i].nxt){

            int w=edge[i].w;

            int t=edge[i].t;

            if(dis[t]>dis[np]+w){

                dis[t]=dis[np]+w;

                ans[t]=ans[np];

                hep.push(make_pair(0-dis[t],t));

            }

            else if(dis[t]==dis[np]+w){

            	ans[t]+=ans[np];

            	ans[t]%=100003;

            }

        }

    }

    for(int i=1;i<=n;i++)

        printf("%d\n",ans[i]);

    return;

}

int main(){

    init();

    dij();

    return 0;

}