1134. 最短路计数（dp思想运用，bfs）

1134. 最短路计数 - AcWing题库

给出一个?N?个顶点?M?条边的无向无权图，顶点编号为?1?到?N。

问从顶点?1?开始，到其他每个点的最短路有几条。

输入格式

第一行包含?2?个正整数?N,M，为图的顶点数与边数。

接下来?M?行，每行两个正整数?x,y，表示有一条顶点?x?连向顶点?y?的边，请注意可能有自环与重边。

输出格式

输出?N?行，每行一个非负整数，第?i?行输出从顶点?1?到顶点?i?有多少条不同的最短路，由于答案有可能会很大，你只需要输出对?100003 取模后的结果即可。

如果无法到达顶点?i?则输出?0。

数据范围

1≤N≤105
1≤M≤2×105

输入样例：

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

输出样例：

1
1
1
2
4

?解析：

最短路问题和dp问题是分不开的。本题运用了dp思想来解决最短路问题。

求某个集合内最优解的方案数的方法：

1.先求出全局最小值是多少。

2.分别求出每个子集中等于全局最小值的元素的个数。

重要结论（也可以自己证明一下）：

1.bfs和Diijkstra算法在出队过程中满足拓扑序

2.bellman_ford和spfa算法不满足拓扑序

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 5, M = 4e5 + 5,mod= 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N], q[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;
	int hh = 0, tt = 1;
	q[0] = 1;
	while (hh < tt) {
		int t = q[hh++];
		if (hh == N)hh = 0;
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > dist[t] + 1) {
				//cout << "___________________" << j << endl;
				dist[j] = dist[t] + 1;
				cnt[j] = cnt[t];
				q[tt++] = j;
				if (tt == N)tt = 0;
			}
			else if (dist[j] == dist[t] + 1) {
				//cout << "_____________________" << j << endl;
				cnt[j] = (cnt[t] + cnt[j]) % mod;
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	for (int i = 1,a,b; i <= m; i++) {
		scanf("%d%d", &a, &b);
		add(a, b), add(b, a);
	}
	bfs();
	for (int i = 1; i <= n; i++) {
		printf("%d\n", cnt[i]);
	}
	return 0;
}

?