题解 Luogu P1144.最短路计数

欢迎访问 My Luogu Space。

【题目大意】

有一张无向无全图，求从1号节点出发到每一个节点的最短路有几条。可能会有重边和自环。

【题解】

由于没有边权，直接用 bfs 从1号节点开始遍历所有的点。并且记 cnt[i] 表示从1号节点到 i 号节点的路径条数，每次 cnt[e[i]]+=cnt[x] 进行统计。

【代码】

// output format !!!
// long long !!!
#include <bits/stdc++.h>
using namespace std;
const int MN = 100000+10;
const int MOD =  100003;

int n, m, cnt[MN], f[MN], dis[MN];
int hed[MN], nex[MN*4], e[MN*4], ct;

int main(){
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; ++i){
		int a, b; scanf("%d%d", &a, &b);
		e[++ct] = b, nex[ct] = hed[a], hed[a] = ct;
		e[++ct] = a, nex[ct] = hed[b], hed[b] = ct;
	}
	queue<int> Q; Q.push(1);
	cnt[1] = f[1] = 1;
	while(!Q.empty()){
		int x = Q.front(); Q.pop();
		for(int i=hed[x]; i; i=nex[i]){
			if(!f[e[i]]){
				f[e[i]] = 1;
				dis[e[i]] = dis[x]+1;
				Q.push(e[i]);
			}
			if(dis[e[i]]==dis[x]+1)
				cnt[e[i]] = (cnt[e[i]]+cnt[x])%MOD;
		}
	}
	for(int i=1; i<=n; ++i)
		printf("%dn", cnt[i]);
	return 0;
}

最后

以上就是忧郁玫瑰为你收集整理的题解 Luogu P1144.最短路计数的全部内容，希望文章能够帮你解决题解 Luogu P1144.最短路计数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。