题目描述
给出一个 $N$ 个顶点 $M$ 条边的无向无权图,顶点编号为 $1$ 到 $N$。
问从顶点 $1$ 开始,到其他每个点的最短路有几条。
输入格式
第一行包含 $2$ 个正整数 $N,M$,为图的顶点数与边数。
接下来 $M$ 行,每行两个正整数 $x,y$,表示有一条顶点 $x$ 连向顶点 $y$ 的边,请注意可能有自环与重边。
输出格式
输出 $N$ 行,每行一个非负整数,第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路,由于答案有可能会很大,你只需要输出对 $100003$ 取模后的结果即可。
如果无法到达顶点 $i$ 则输出 $0$。
数据范围
$1 \leq N \leq 10^5, 1 \leq M \leq 2 * 10^5$
输入样例
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出样例
1
1
1
2
4
算法
(BFS) $O(n)$
- $DP$要求状态转移的关系是拓扑序,图中可能有环,不满足拓扑序
- 图的最短路径可以构成一棵最短路树(拓扑图)
- $BFS$每个点只入队一次,出队一次,满足拓扑序;$Dijkstra$每个点第一次出队的序列也满足拓扑序;$SPFA$每个点可能会进队出队多次,不满足拓扑序
- 在做BFS或者Dijkstra枚举邻接点时,有两种情况:
- $dist[j] > dist[t] + 1$:到达$j$的最短路个数和到达$t$是一样的
- $dist[j] = dist[t] + 1$:到达$j$的最短路个数应该加上到达$t$的最短路个数,从$t$经过的最短路,在$j$上经过的时候也是最短路
时间复杂度
如果用$BFS$做,每个点只会入队出队一次,时间复杂度是$O(n)$;如果用堆优化$Dijkstra$做,时间复杂度为$O(mlog(n))$
C++ 代码
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 4e5 + 10, mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0, cnt[1] = 1;
queue<int> q;
q.push(1);
while (q.size()) {
int t = q.front(); q.pop();
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + 1) {
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q.push(j);
} else if (dist[j] == dist[t] + 1) {
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m -- ) {
int a, b; cin >> a >> b;
add(a, b), add(b, a);
}
bfs();
for (int i = 1; i <= n; i ++ ) cout << cnt[i] << endl;
return 0;
}