AcWing1134/洛谷P1144 最短路计数

AcWing传送门
洛谷传送门

题目大意

\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\sim n\))的最短路数量

解题思路

\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题
\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)
\(\qquad\)\(1.\)当\(dist_{\ j} < dist_{\ i} + 1\)的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge 必定没有i}\)，所以我们可以直接忽视这种情况
\(\qquad\)\(2.\)当\(dist_{\ j} \ge dist_{\ i} + 1\)的时候，我们继续分成两类

\(\qquad \qquad \color{#0000ff}{\large a.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表着\(i\)可以是\(1\sim j\)的最短路中的一个点，但是还有其它点，这里根据 加法原理 就可以得出我们\(cnt_{\ j}\)应该加上\(cnt_{\ i}\)（因为从\(1\sim i\)的任意一条最短路，再加上\(i\sim j\)这条边，都属于\(1\sim j\)的最短路）。
\(\qquad \qquad \color{#0000ff}{\large b.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表\(i\)是目前第一个可以更新\(j\)的点，所以\(j\)是第一次被更新，需要入队，其它的操作和分类\(\color{#0000ff}{\large a}\)都是一样的

代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N << 2, mod = 1e5 + 3;
int dist[N], n, m, cnt[N];
int h[N], e[M], ne[M], idx;

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

void bfs() 
{
    memset(dist, 0x3f, sizeof dist);
    queue <int> q;
    
    dist[1] = 0, cnt[1] = 1, q.push(1);
    
    while (q.size()) 
    {
        auto t = q.front(); q.pop();
        
        for (int i = h[t]; ~i; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q.push(j);
            }
            else if (dist[j] == dist[t] + 1) 
                cnt[j] = (cnt[j] + cnt[t]) % mod;
        }
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    while (m -- ) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    
    bfs();
    
    for (int i = 1; i <= n; i ++ ) 
        printf("%d\n", cnt[i]);
    
    return 0;
}