luoguP1144 最短路计数

因为边权都是 1 ，直接可以用BFS来求最短路

在BFS的过程中，如果当前层可以由上一层转化过来，就进行计数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10,M = 2e6 + 10,mod = 100003;
int e[M],ne[M],h[N],idx,cnt[N],n,m,depth[N];
bool st[N];
void add(int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void bfs() {
    queue<int> q;
    q.push(1);
    depth[1] = 0;
    cnt[1] = 1;
    st[1] = 1;
    while(q.size()) {
        int t = q.front();
        q.pop();
        for(int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(!st[j]) {
                st[j] = 1;
                depth[j] = depth[t] + 1;
                q.push(j);
            }
            if(depth[j] == depth[t] + 1) {
                cnt[j] = (cnt[t] + cnt[j]) % mod;
            }
        }
    }
}
int main() {
    memset(h,-1,sizeof h);
    cin >> n >> m;
    for(int i = 0;i < m; ++i) {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    bfs();
    for(int i = 1;i <= n; ++i) cout << cnt[i] << endl ;
    return 0;
}

luoguP1144 最短路计数

原文：https://www.cnblogs.com/lukelmouse/p/13174040.html