题面：最短路计数
大秦为你打开题目传送门
题目描述
给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。
输入格式
第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。
接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条连接顶点 $x$ 和顶点 $y$ 的边，请注意可能有自环与重边。
输出格式
共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
8
| 5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
|
样例输出 #1
提示
$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。
对于 $20\%$ 的数据，$1\le N \le 100$；
对于 $60\%$ 的数据，$1\le N \le 10^3$；
对于 $100\%$ 的数据，$1\le N\le10^6$，$1\le M\le 2\times 10^6$。
思路
这道题是无权无向图，不难想到其实方案数肯定还是很多的，我们记录 $cnt[x]$ 表示点 $1\rightarrow x$ 的最短路数量。那么如果走到这个点，更新了最短路，那么就应该是和走过来那个点的数量一样，因为他那里那么多的数量都是可以连一条边过来的。如果没有更新，但也遇到了一样的，就累加，同理的。
代码
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
100
101
102
103
104
105
106
107
108
109
110
111
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int MaxV = 1e6 + 10;
const int MaxE = 2e6 + 10;
const int P = 100003;
template<int N, int M>
class Graph {
private :
struct Edge {
int to, nt, wt;
Edge() {}
Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[M];
int hd[N], cnte;
public :
inline void AddEdge(int u, int v, int w = 0) {
e[++cnte] = Edge(v, hd[u], w);
hd[u] = cnte;
}
inline int head(int u) { return hd[u]; }
inline int nt(int u) { return e[u].nt; }
inline int to(int u) { return e[u].to; }
inline int wt(int u) { return e[u].wt; }
};
int n, m;
Graph< MaxV, MaxE << 1 >G;
inline void Input() {
read(n, m);
int u, v;
for(int i = 1; i <= m; i++) {
read(u, v);
G.AddEdge(u, v);
G.AddEdge(v, u);
}
}
int dis[MaxV], cnt[MaxV];
int vis[MaxV];
inline void Dijkstra() {
priority_queue<pii, vector<pii >, greater<pii > >q;
q.push(make_pair(0, 1));
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0; cnt[1] = 1;
while(!q.empty()) {
int u = q.top().second; q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = G.head(u); i; i = G.nt(i)) {
int v = G.to(i), nd = dis[u] + 1;
if(dis[v] == nd) {
(cnt[v] += cnt[u]) %= P;
}
if(dis[v] > nd) {
dis[v] = nd; cnt[v] = cnt[u];
q.push(make_pair(dis[v], v));
}
}
}
}
inline void Work() {
Dijkstra();
for(int i = 1; i <= n; i++) {
printf("%d\n", cnt[i]);
}
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
