#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;

const int maxn=1000000+1,maxm=2000000+1,INF=0x7f7f7f7f,MOD=100003;
vector<int>G[maxn];int dep[maxn];bool vis[maxn];int cnt[maxn];

int main(){
    int N,M;scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++){
        int x,y;scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    queue<int>Q;dep[1]=0;vis[1]=1;Q.push(1);cnt[1]=1;
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0;i<G[x].size();i++){
            int t=G[x][i];
            if(!vis[t]){vis[t]=1;dep[t]=dep[x]+1;Q.push(t);}
            if(dep[t]==dep[x]+1){cnt[t]=(cnt[t]+cnt[x])%MOD;}
        }
    }
    for(int i=1;i<=N;i++){
        printf("%d\n",cnt[i]);
    }
    return 0;
}

看到别的大佬的题解都是直接发代码，我来说说思路。

我们可以使用 BFS 记录当前的最短路线，而最先找到的路线一定就是最优解，因为 BFS 搜索树的深度就是最短路距离。

所以，我们可以使用类似 DP 的解法，记录 1 号节点到这个节点的距离。

BFS 遍历到这个节点时，记录答案

AC 代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MOD 100003
using namespace std;
int ans[1000005], sp[1000005]; // ans数组表示答案，sp[i]表示到达节点i的最短路
bool vis[1000005]; // 判断是否走过
vector<int> p[1000005]; // 邻接表见图
void bfs() {
    queue<int> q;
    vis[1] = true;
    q.push(1);
    ans[1] = 1;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = 0; i < p[x].size(); i++) {
            int t = p[x][i];
            if (!vis[t]) { // 如果没走过这个节点
                vis[t] = true;
                sp[t] = sp[x] + 1;
                q.push(t);
            }
            if (sp[t] == sp[x] + 1) {
                ans[t] = (ans[t] + ans[x]) % MOD;
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false); // 读写优化
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if (u != v) {
            p[u].push_back(v);
            p[v].push_back(u);
        }
    }
    bfs();
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}