标签：SPFA
题目
题目描述
给出一个\(N\)个顶点\(M\)条边的无向无权图，顶点编号为\(1-N\)。问从顶点\(1\)开始，到其他每个点的最短路有几条。
输入输出格式
输入格式
第一行包含\(2\)个正整数\(N,M\)，为图的顶点数与边数。
接下来\(M\)行，每行\(2\)个正整数\(x,y\)，表示有一条顶点\(x\)连向顶点\(y\)的边，请注意可能有自环与重边。
输出格式
共\(N\)行，每行一个非负整数，第\(i\)行输出从顶点\(1\)到顶点\(i\)有多少条不同的最短路，由于答案有可能会很大，你只需要输出\(ans \bmod 100003\)后的结果即可。如果无法到达顶点\(i\)则输出\(0\)。
输入输出样例
输入样例#1
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出样例#1
1
1
1
2
4
说明
\(1\)到\(5\)的最短路有\(4\)条，分别为\(2\)条\(1-2-4-5\)和\(2\)条\(1-3-4-5\)（由于\(4-5\)的边有\(2\)条）。
对于\(20\%\)的数据，\(N ≤ 100\)；
对于\(60\%\)的数据，\(N ≤ 1000\)；
对于\(100\%\)的数据，\(N<=1000000,M<=2000000\)。
分析
SPFA模板
加上一个统计数组即可
如果更新最短路，那么同时更新统计数组（注意是加法）
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6,mod=100003;
struct edge{int to,next;}e[maxn<<1];
int last[maxn],dis[maxn],num[maxn],n,m,cnt=0,inque[maxn],que[maxn<<2];
void insert(int u,int v){e[++cnt]=(edge){v,last[u]};last[u]=cnt;}
#define v e[i].to
void SPFA(){
mem(dis,0x3f3f3f);
int head=0,tail=1;
num[1]=1;dis[1]=0;inque[1]=1;que[head]=1;
while(head<tail){
int now=que[head++];
reg(now){
// cout<<now<<' '<<e[i].to<<' '<<e[i].next<<endl;
if(dis[v]==dis[now]+1)num[v]+=num[now],num[v]%=mod;
else if(dis[v]>dis[now]+1){
dis[v]=dis[now]+1;
que[tail++]=v;inque[v]=1;
num[v]=num[now];
}
}
inque[now]=0;
}
}
int main()
{
n=read(),m=read();
rep(i,1,m){
int x=read(),y=read();
if(x==y)continue;
insert(x,y);insert(y,x);
}
SPFA();
rep(i,1,n)cout<<num[i]<<endl;
return 0;
}
