最短路计数

从起点出发，BFS遍历，每到一个点，若之前未访问过，就标记，当前到它的最短路径条数即为该路径上他的父节点的条数；否则比较从当前路径走所得到的与起点的距离和最短路径大小，（此时最短路径大小已知，见上文）若相等，它的最短路径条数加上该路径上它父节点路径数 。

起点到某一点最短路路径条数等于起点到它所有父节点路径条数的和。讲的有些赘余，代码思路比较清晰，可以参考，如果还不懂可以画一下样例： 从起点开始走，每到一个点就标记，并标上它到起点的最短距离和它的路径数，直到遍历全图。

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int mod=1e5+3;
int head[1000005],nxt[4000005],to[4000005],cnt=0;
int n,m;
int vis[1000005];
int ans[1000005],dep[1000005];
queue<int> q;
void add(int x,int y){
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y;
    ans[1]=1;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    q.push(1);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int i=head[u];i;i=nxt[i]){
            int t=to[i];
            if (!vis[t]) {
                vis[t]=1;
                dep[t]=dep[u]+1;
                q.push(t);
            }
            if (dep[t]==dep[u]+1){
                ans[t]=(ans[t]+ans[u])%mod;
            }
        }
    }
    ans[1]=1;
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}