洛谷P1144 最短路计数

由于是无权图所以搜索树的层数就是节点到根的最短路径长度
用dp[]代表节点的最短路径数量
某个节点的最短路径总数等于上一层所有能到达此节点的最短路径总数之和


#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 100003;
const int N = 1000010 , M = 2000020;
int idx, e[M], ne[M], h[N];
int vis[N], dp[N];  //vis 节点的层数
int n, m;

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

void bfs()
{
    queue<int> q;
    q.push( 1 );
    vis[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( !vis[j] )
            {
                vis[j] = vis[t] + 1;
                q.push( j );
                dp[j] += dp[t] % mod;
            }
            else if( vis[j] == vis[t] + 1 )
                dp[j] += dp[t] % mod;
        }
    }
}

signed main()
{
    cin >> n >> m;

    memset( h, 0, sizeof h );
    memset( vis, 0, sizeof vis);
    memset( dp, 0, sizeof dp);
    for( int i = 0; i < m; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if( x != y )
        {
            add( x, y );
            add( y, x );
        }
    }

    dp[1] = 1;
    bfs();

    for( int i = 1; i <= n; i ++ )
        cout << dp[i] % mod << endl;
}