最短路计数（松弛操作处理）

题目链接

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
#include
#include
#include
#include
#include
using namespace std;

#define PII pair

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

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

void DJ(int s){
	for(int i = 1;i >n>>m;
	int u,v,w;
	for(int i = 1;i >u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	DJ(1);
	for(int i = 1;i