跑Dijkstra的时候顺便记录一下每个节点的最短路径的数目，

			if (dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				num[v] = (num[v] + num[u]) % MOD;
				q.push(P(dist[v], v));
			}
			else if (dist[v] == dist[u] + 1)
				num[v] = (num[v] + num[u]) % MOD;

如果是新的最短路径，那么到v的路径数目等于到其上一个节点u的路径数目，如果找到一个节点到v的最短路和当前相等，那么将u的路径数目也加上

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 100006
#define vec vector<int>
#define P pair<int,int>
#define MOD 100003

int N, M, dist[MAX], num[MAX], x, y;
vec G[MAX];

void dijstra(int s) {
	fill(dist, dist + MAX, inf);
	memset(num, 0, sizeof(num));
	priority_queue<P, vector<P>, greater<P> >q;
	q.push(P(0, s)); dist[s] = 0; num[s] = 1;
	while (!q.empty()) {
		int u = q.top().second, d = q.top().first; q.pop();
		if (dist[u] < d)continue;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			if (dist[v] > dist[u] + 1) {
				dist[v] = dist[u] + 1;
				num[v] = (num[v] + num[u]) % MO...