[Luogu P1144]最短路计数

emmmm这个题看起来非常复杂，实际上仔细一分析发现到一个点最短路的个数就是所有前驱最短路个数之和。如果在图上表示也就是以1为根的bfs搜索树，一个点的最短路个数等于每一个能够向它扩展的所有点的最短路个数之和。SPFA可以实现bfs。

先看代码吧

我们用ans数组存储每个点最短路个数。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#define N 4000010
#define mod 100003
#define inf 400000000
int head[N],nxt[N],to[N],dis[N],ans[N];
bool vis[N];
int n,m,cnt;
void add(int u,int v)
{
    cnt++;
    nxt[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;//之前debug就因为这个地方写错了QAQ
    return;
}
using namespace std;
void spfa()
{
    for(int i = 1;i <= n;i++) dis[i] = inf;
    queue<int>q;
    ans[1] = 1;
    vis[1] = 1;
    dis[1] = 0;
    q.push(1);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i];
            if(dis[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                ans[v] = ans[u];//点u第一次扩展到了v，则v的最短路个数为u的最短路个数
                if(!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
            else if(dis[v] == dis[u] + 1)//如果另外的点扩展到了点v
            {
                ans[v] += ans[u];//v的最短路个数再加上扩展来的点的最短路个数
                ans[v] %= mod;
            }
        }
    }
    return;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);
        add(v,u);
    }
    spfa();
    for(int i = 1;i <= n;i++)
    {
        printf("%d
",ans[i] % mod);
    }
    return 0;
}