提供一个 top-down 的记忆化搜索的写法

感觉这题用记忆化搜索是比较好写的。

步骤：

1. 用 BFS 求得每个点到起点的最短距离；
2. 记忆化搜索;

具体来说，一个到起点距离为 d 的点的最短路径只能从相邻的 距离为 d-1 的点转移过来，所以递归搜索这种点再求和取模就好了，注意初始化。

参考代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
const int M = 4*N;
const int MOD = 100003;
int h[N], e[M], ne[M], dist[N], idx, n, m;
int cnt[N];
bool st[N], bfs_st[N];
void init() {
    memset(dist, 0x3f3f3f3f, sizeof dist);
    memset(h, -1, sizeof h);
    cnt[1] = 1;
    dist[1] = 0;
    st[1] = true;
}

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int get(int node) {
    if(st[node]) return cnt[node];
    else {
        int res = 0;
        int d = dist[node];
        for(int i = h[node]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] != d - 1) continue;
            res += get(j);
            res %= MOD;
        }
        cnt[node] = res;
        st[node] = true;
        return res;
    }
}

void bfs() {
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        for(int i = h[curr]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] <= dist[curr] + 1) continue;
            dist[j] = dist[curr] + 1;
            q.push(j);
        }
    }
}

int main() {
    cin >> n >> m;
    init();
    int a, b;
    for(int i = 1; i <= m; i ++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    bfs();
    for(int i = 1; i <= n; i ++) {
        cout << get(i) << endl;
    }
    return 0;
}