题目链接

https://www.luogu.com.cn/problem/P1144

思路

我们用一个ans数组存储我们从源点到当前点的路径条数，那么我们发现如果我们能进行松弛操作，我们当前的最短路路径就可以从上一个点继承过来即 a n s [ j ] = a n s [ t ] ans[j]=ans[t] ans[j]=ans[t]，如果不能进行松弛操作，那么我们查看是否和当前的最短路长度相等（当然这里的边权都是1不影响），如果相等的话那么我们就更新 a n s [ j ] ans[j] ans[j]的值即 a n s [ j ] = ( a n s [ j ] + a n s [ t ] )   %   m o d ans[j]=(ans[j] + ans[t]) \ \% \ mod ans[j]=(ans[j]+ans[t]) % mod

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

#define PII pair<int,int>

const int INF = 0x3f3f3f3f;
const int mod = 100003;
const int N = 1000000 + 10;

vector<int> E[N];
int dis[N],n,m,ans[N];
bool vis[N];

void DJ(int s){
	for(int i = 1;i <= n; ++i) dis[i] = INF,ans[i] = 0,vis[i] = false;
	queue<int> que;
	dis[s] = 0;
	que.push(s);
	ans[1] = 1;
	while(!que.empty()){
		int t = que.front();
		que.pop();
		if(vis[t]) continue;
		vis[t] = true;
		for(int i = 0,l = E[t].size();i < l; ++i) {
			int j = E[t][i];
			if(dis[j] > dis[t] + 1){
				dis[j] = dis[t] + 1;
				ans[j] = ans[t];
				que.push(j);
			}
			else if(dis[j] == dis[t] + 1) ans[j] = (ans[j] + ans[t]) % mod;
		}
	}
}

int main()
{
	cin>>n>>m;
	int u,v,w;
	for(int i = 1;i <= m; ++i) {
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	DJ(1);
	for(int i = 1;i <= n; ++i) cout<<ans[i]<<endl;
	
}