最短路计数
题目链接：
最短路计数
题目概述&解题思路：
字面意思，不多做解释。求出所有的最短路个数，对 $10^6+3$ 取模。当然，如果起点到编号为 $i$ 的点不连通当然数目就为0啦。
对于简单的思路，那就是跑出最短路，再跑一遍遍历，看有多少种情况能够走到 $i$ 点，然后统计。但是这样是绝对会超时的
对于 $100%$ 的数据, $N ≦ 1000000,M ≦ 2000000$ .所以我们应该选择 SPFA ，啊对，就是选择SPFA，有些算法死了，它还活着。
我们可以用一个数组 $AnsL$ 来存储从 $1$ 号点到第 $i$ 号点的最短路个数，然后一边跑 $SPFA$ 一边修改 $AnsL$ 的值，即当我们当前从 $u$ 点跑到了 $v$ 点的话费与 $Dist_v$ 的值相同时，那么现在是一条目前找到的最短路（之后可能会存在更短路），那么就有：
$Ans_v=Ans_u+1$
的推导公式。
而如果我们找到了更短路，那就把当前点的计数清零。从 $u$ 点出发到的 $v$ 点的路即是最短路（目前），则传递答案为：
1
2
| Dist[v]=Dist[u]+1;
Ans[v]=AnsL[v]=Ans[u];
|
这就是两种传递的方式，也就是本题最关键的代码核心。
其他的注意事项则在代码里体现：
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
using namespace std;
using std::cin;
using std::cout;
int N,M,x,y,Cnt;
int Dis[1000001];
bool Vis[1000001];
int Ans[1000001];
int AnsL[1000001];
int First[1000001];
struct Node
{
int To,Next;
}Edge[2000001];
inline void SPFA(int x)
{
Dis[x]=0;
Vis[x]=1;
queue<int>Q;
Q.push(x);
while(!Q.empty())
{
int u=Q.front();
for(int e=First[u];e;e=Edge[e].Next)
{
int Now=Edge[e].To;
if(Dis[Now]>Dis[u]+1)
{
Dis[Now]=Dis[u]+1;
Ans[Now]=AnsL[Now]=Ans[u]%100003;
if(!Vis[Now])
{
Vis[Now]=1;
Q.push(Now);
}
}
else if(Dis[Now]==Dis[u]+1)
{
AnsL[Now]=(AnsL[Now]+Ans[u])%100003;
Ans[Now]=(Ans[Now]+Ans[u])%100003;
if(!Vis[Now])
{
Vis[Now]=1;
Q.push(Now);
}
}
}
Ans[u]=0;
Q.pop();
Vis[u]=0;
}
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d%d",&x,&y);
Edge[++Cnt].To=y;
Edge[Cnt].Next=First[x];
First[x]=Cnt;
Edge[++Cnt].To=x;
Edge[Cnt].Next=First[y];
First[y]=Cnt;
}
AnsL[1]=Ans[1]=1;
for(int i=1;i<=N;++i)
{
Dis[i]=0x7f7f7f7f;
}
SPFA(1);
for(int i=1;i<=N;++i)
{
printf("%d\n",AnsL[i]);
}
return 0;
}
|