Analysis
求最短路我们都会求，但是求最短路径条数呢？
不难发现 bfs 是按层搜的，所以它一定能求出从一个点到图上任意一个点的最短路。
若设 \(x\) 为当前点， \(x-y\) 为一条边，若 \(x\) 的最短路等于 \(y\) 的最短路+1，则 \(x-y\) 一定是一条最短路。类似于 dp \(ans_x + ans_y\) 即可。
容易发现本题渗透了 dp 的思想，在 bfs 跑最短路的同时 dp。
代码如下。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define N 1000010
using namespace std;
const int mod = 100003;
vector <int> Edge[N];
int vis[N],cnt[N];
int ans[N];
int res[N];;
int n,m;
void bfs()
{
queue <int> q;
q.push(1);
vis[1] = 1;
res[1] = 1;
while(!q.empty())
{
int now = q.front();
q.pop();
for(int j=0;j<Edge[now].size();j++)
{
if(!vis[Edge[now][j]])
{
q.push(Edge[now][j]);
ans[Edge[now][j]] = ans[now] + 1;
vis[Edge[now][j]] = 1;
}
if(ans[Edge[now][j]] == ans[now]+1)
{
res[Edge[now][j]] = (res[Edge[now][j]]+res[now])%mod;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Edge[x].push_back(y);
Edge[y].push_back(x);
}
bfs();
for(int i=1;i<=n;i++) cout<<res[i]<<endl;
return 0;
}