假设每条边的权值都为1,链式前向星存图
加一个数组pre[i]记录到i这个点有几种走法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define gold_m main
#define re register
#define Accept return 0;
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//const int inf =0x3f3f3f3f;
const ll inf =0x3f3f3f3f3f3f3f;
const int maxn=1e6+10;
const int mod=100003;
const int N =1e6+10;
//const long double PI=3.1415926535897932384626433832795;
//const long double e=2.71828182845904523536028747135266;
typedef pair<ll,ll>PII;
inline ll read() {
ll x=0;
bool f=0;
char ch=getchar();
while (ch<'0'||'9'<ch) f|=ch=='-', ch=getchar();
while ('0'<=ch && ch<='9')
x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
//priority_queue<int,vector<int>, greater<int> >heap;
priority_queue<PII,vector<PII> ,greater<PII> >q;
stack<int>st;
ll cnt,head[maxn],pre[maxn],dist[maxn],vis[maxn],n,m;
struct wmy{
ll u,v,w,next;
}e[maxn];
void add(int u, int v)
{
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=1;
e[cnt].next=head[u];
head[u]=cnt++;
}
void Dijkstra(){
for(int i=1 ;i<=n;i++) dist[i]=inf;
dist[1]=0;
// vis[1]=1;
pre[1]=1;
q.push({0,1});
while(q.size())
{
auto t=q.top();
q.pop();
ll fr=t.first;
ll se=t.second;
if(vis[se]) continue;
vis[se]=1;
// fi=distanct
// se 点
for(int i=head[se];i!=-1;i=e[i].next)
{
ll v=e[i].v;
if(dist[v]>dist[se]+1)
{
dist[v]=dist[se]+1;
pre[v]=pre[se];
q.push({dist[v],v});
}
else if(dist[v]==dist[se]+1)
{
pre[v]=(pre[v]+pre[se])%mod;
}
}
}
}
int gold_m() {
memset(head,-1,sizeof(head));
// memset(pre,1,sizeof(pre));
n=read();
m=read();
for(int i=1 ;i<=m;i++)
{
ll u,v,w;
u=read();
v=read();
add(u,v);
add(v,u);
}
Dijkstra();
for(int i=1 ;i<=n;i++)
if(dist[i]!=inf)
cout<<pre[i]%mod<<endl;
else cout<<"0"<<endl;
Accept;
}
/*
https://pasteme.cn/28763
*/