虽然题目叫最短路计数，但是TA可以只用到最短路的概念而不用最短路的算法……
由于这是一个无权图，所以一条路径上边的数量就是这条路径的长度，那么我们就可以用BFS来搞定这个问题了。
具体思路
我们每遍历到一个节点就和ta的前一个结点的距离比较，这里会有三种情况：(由1到2)
- 2号点没有被访问过||time[1] + 1 < time[2]：此时我们直接用1号点的信息去更新2就好啦
- time[1] + 1 = time[2] : 这个我们就只需要更新一下ans就可以啦
- time[1] + 1 > time[2] :此时这条路径比之前的某条路径要长，直接跳过就可以啦
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
using namespace std;
int read()
{
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
queue<int> que;
struct edge{
int next,to,v;
}e[2000005];
int n,m,cnt,x,now,y,tim[2000000],ans[2000000],d[2000000];
inline int add(int x,int y)
{
e[++cnt].to = y;
e[cnt].next = d[x];
d[x] = cnt;
}
int main()
{
n = read();
m = read();
for(re int i = 1; i <= m; i++)
{
x = read(); y = read();
add(x,y); add(y,x);
}
que.push(1);
ans[1] = 1;
while(!que.empty())
{
now = que.front();
que.pop();
for(re int i = d[now]; i; i = e[i].next)
{
if(tim[now] + 1 < tim[e[i].to] || tim[e[i].to] == 0)
{
tim[e[i].to] = tim[now] + 1;
ans[e[i].to] = ans[now];
que.push(e[i].to);
}
else
if(tim[now] + 1 == tim[e[i].to]) ans[e[i].to] = (ans[e[i].to] + ans[now]) % 100003;
}
}
ans[1] = 1;
for(re int i = 1; i <= n; i++) printf("%d\n",ans[i]);
return 0;
}
