题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

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

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条有连结 $x$ 和 $y$ 的无向边，请注意可能有自环与重边。

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。

解题思路分析

有几个解题信息：

1. 这条题是没有负权边，每条边的权都是 1，所以，如果出现环，那么肯定就是会出现更大的步数到大这个点。我们可以通过步数来排除环。

2. 解决了环的问题的情况下，从顶点 1 走到顶点 k，可以基于 spfa 算法。但是，spfa 算法里面的细节要理解得更透彻。比方说，顶点 1 到 顶点 5，可能有多种走法。第一种走法是 1->3->5, 我们找到这个走法的时候，意味着有多少种走法走到 3 ，就有多少种走法走到 5；后面，我们可能找到了一种新的走法 1->4->5 ，这个时候，我们其实是叠加新的走法，在原来的方案数的基础上加上走到顶点 4 的方案数（这里还有同余定理，要对 100003 模运算）

这条题就类似于以前的 BFS 算法，小老鼠走迷宫，从起点开始往外一步步的走，但是只关心最段露泾的方案。

样例

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

1
1
1
2
4

提示

$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据，$1\le N \le 100$；

对于 $60\%$ 的数据，$1\le N \le 10^3$；

对于 $100\%$ 的数据，$1\le N\le10^6$，$1\le M\le 2\times 10^6$。

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,m,tot,step[1000001],ans[1000001],h[1000001];
queue <int> q;
bool f[1000001];
struct Edge
{
	int v,next;
}e[4000001];
void spfa()
{
	memset(step,0x3f,sizeof(step));
	q.push(1);
	step[1] = 1;
	ans[1] = 1;
	f[1] = true;

	int t;
	while(q.size())
	{
		t = q.front();
		q.pop();
		f[t] = false;
		for(int i=填空(1);填空(2);i=填空(3))
		{
			if(填空(4))
			{
				step[填空(5)] = step[t]+1;
				ans[填空(5)] = (填空(6))%100003;

				if(!f[填空(5)])
				{
					q.push(填空(5));
					f[填空(5)] = true;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		
		e[++tot].v=y;
		e[tot].next = 填空(7);
		填空(7) = tot;
		
		e[++tot].v=x;
		e[tot].next = 填空(8);
		填空(8) = tot;
	}
	spfa();

	for(int i=1;i<=n;i++)
		printf("%d\n",ans[i]);

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}