这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 1314 个字，阅读时长 ≈ 4 分钟

P1144 最短路计数

题目链接

题意

一个 N 个点 M 条边的无向图，顶点编号为 $1\sim N$ ，问从顶点1开始，到其他每个点的最短路有几条。

思路

一个最短路计数的板子题，基本随便一个单源最短路算法如 spfa，dijkstra 等都可以，因为边权为1也可以使用 bfs。这里讲解一个 bfs 的解法因为dij没调出来。

因为边权为1，所以从1开始遍历到这个点的深度即为1到这个点的最短路，最短路的数量统计其实蛮简单的，如果从点1经过这个点A到达另一个点B的路径长度等于从点1到达点B的最短路长度，那么点B的最短路个数就加上点A的最短路个数即可。记得取模

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=100005,M=400005,mod=100003,inf=INT_MAX>>1;
int n,m;
int idx=1,head[N],to[M],nxt[M];
int cnt[N],dis[N];
bool vis[N];
typedef pair<int,int> pii;
bool operator <(pii a,pii b){
    return b.first<a.first;
}
void addedge(int u,int v){
    to[++idx]=v;
    nxt[idx]=head[u];
    head[u]=idx;
}
queue<pii> q;
void bfs(){
    pii p;
    q.emplace((pii){0,1});
    //队列q可以用Int数组只存下标，但是懒得改了（
    vis[1]=1;
    dis[1]=0;
    cnt[1]=1;
    int u,d,v;
    while(!q.empty()){
        p=q.front();
        q.pop();
        u=p.second,d=p.first+1;
        for(int i=head[u];i;i=nxt[i]){
            v=to[i];
            if(!vis[v]){
                vis[v]=1;
                q.emplace((pii){d,v});
                dis[v]=d;
            }
            if(dis[v]==d){
                //更新最短路个数
                cnt[v]+=cnt[u];
                cnt[v]%=mod;
            }
        }
    }
}
int main()
{
    n=read();
    m=read();
    for(int i=0;i<=n;++i) dis[i]=inf;
    int u,v;
    for(int i=0;i<m;++i){
        u=read(); v=read();
        if(u==v) continue;
        addedge(u,v);
        addedge(v,u);
    }
    bfs();
    for(int i=1;i<=n;++i){
        printf("%d\n",cnt[i]);
    }
    return 0;
}