对于边权都为相同的图，求最短路可以用bfs
#include#include #include #include using namespace std;struct node{ int point; int nxt;};node line[4000100];int head[1000100],tail;int sest[1000100],num[1000100];queue q;void add(int x,int y){ line[++tail].point=y; line[tail].nxt=head[x]; head[x]=tail;}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) sest[i]=0x7fffffff; int a,b; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } sest[1]=0; num[1]=1; q.push(1); int pass; while(!q.empty()) { pass=q.front(); q.pop(); for(int i=head[pass];i;i=line[i].nxt) { if(sest[line[i].point]>sest[pass]+1) { sest[line[i].point]=sest[pass]+1; num[line[i].point]=num[pass]%100003; q.push(line[i].point); continue; } if(sest[line[i].point]==sest[pass]+1) num[line[i].point]=(num[line[i].point]+num[pass])%100003; } } for(int i=1;i<=n;i++) printf("%d\n",num[i]%100003);}