本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-12-10 19:39:04

这是一个很lj的题解

难度：$\color{green}\text{普及+/提高}$

$\color{green}\text{AC算法}$：$dijkstra$

题目分析：

根据题目，让求的是从从顶点$1$到其他$n-1$个点的最短路有多少条。既然是要求最短路，肯定要用到$dijkstra$。然后开一个数组$ans[maxn]$来记录到第$i$个点有多少条最短路。在$dijkstra$中在更新最短距离时顺手更新$ans[i]$即可。

具体做法：

$dijkstra$相信大佬们都会，那么如何更新$ans[i]$呢？首先$ans[to]$肯定是使用$ans[u]$来更新，因为$ans[to]$的最短路数肯定就包含$ans[u]$（这不是废话吗)。

$dijkstra$更新最短距离时，如果发现$dis[to] > dis[u] + 1$，也就是说当前点$u \rightarrow to$不是最短距离，之前统计的到$to$的最短数($ans[to]$)肯定都要全部作废，也就是：

ans[to] = ans[u];

如果是当前距离就是最短距离，那么直接加上从$u$转移过来的路径数($ans[u]$)即可，也就是：

ans[to] += ans[u];

到此，本题就做完了，要记得取模。下面是代码：

#include <bits\/stdc++.h>
using namespace std;
#define reg register
const int maxn=1e6+5;
const int maxm=4e6+5;
int n,m;
int dis[maxn];
int head[maxn];
int ans[maxn];
bool vis[maxn];
struct EDGE
{
	int to,nxt;
}edge[maxm];
int tot;
inline void add(int u,int to)
{
	edge[++tot].to=to;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void solve()
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	priority_queue< pair<int,int> > que;
	que.push(make_pair(0,1));
	dis[1]=0;
	ans[1]=1;
	reg int u;
	while(!que.empty())
	{
		u=que.top().second;
		que.pop();
		if(vis[u])continue;
		vis[u]=1;
		reg int to;
		for(reg int i=head[u];i;i=edge[i].nxt)
		{
			to=edge[i].to;
			if(dis[to]>dis[u]+1)
			{
				dis[to]=dis[u]+1;
				ans[to]=ans[u];
				que.push(make_pair(-dis[to],to));
			}
			else if(dis[to]==dis[u]+1)
			{
				ans[to]+=ans[u];
				ans[to]%=100003;
			}
		}
	}
	for(reg int i=1;i<=n;i++)
	{
		printf("%d\n",ans[i]);
	}
}
int main()
{
	n=read();
	m=read();
	reg int x,y;
	for(reg int i=1;i<=m;i++)
	{
		x=read();
		y=read();
		add(x,y);
		add(y,x);
	}
	solve();
	return 0;
}