水题链接：https://www.luogu.org/problemnew/show/P1144
这道题就是很水啊，水到我居然不用最短路算法就做了出来。因为每条边的权值都为1，最短路计数，无异于遍历整张图，记录有多少个结点可以到达这个点，且路径长度为最小的那个。用BFS，保证第一次访问到结点时的路径长度就是到起点的最短路，后面只需要加个条件判断就行。其实SPFA、Dijkstra堆优化也可以，就是懒得去写，他只需要求最短路并且统计最短路到每个结点的次数就可以了（当然因为本题的边权都为1）。另外他说有重边，这个没关系，还说有自环，就吓到我了（怎么可能），所以加上一个当前弧优化QwQ。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 inline int get_num() { 7 int num; 8 char c; 9 while((c=getchar())==‘\n‘||c==‘ ‘||c==‘\r‘); 10 num=c-‘0‘; 11 while(isdigit(c=getchar())) num=num*10+c-‘0‘; 12 return num; 13 } 14 void put_num(int i) { 15 if(i>9) put_num(i/10); 16 putchar(i%10+‘0‘); 17 } 18 const int maxn=1e6+5,maxm=4e6+5,inf=0x3f3f3f3f; 19 int n,m,head[maxn],eid,vis[maxn],d[maxn],cnt[maxn]; 20 struct edge { 21 int v,next; 22 } E[maxm]; 23 void insert(int u,int v) { 24 E[eid].v=v; 25 E[eid].next=head[u]; 26 head[u]=eid++; 27 } 28 queue<int> q; 29 void bfs() { 30 memset(d,inf,sizeof(d)); 31 d[1]=0; 32 cnt[1]=1; //看样例的意思，1的最短路条数开始就是1 33 q.push(1); 34 while(!q.empty()) { 35 int u=q.front();q.pop(); 36 if(vis[u]) continue; 37 vis[u]=1; 38 for(int& p=head[u];p+1;p=E[p].next) { 39 int v=E[p].v; //答案要求mod 100003 40 if(d[v]==d[u]+1) cnt[v]+=cnt[u],cnt[v]%=100003; 41 if(d[v]==inf) d[v]=d[u]+1,cnt[v]+=cnt[u],cnt[v]%=100003; 42 q.push(v); 43 } 44 } 45 } 46 int main() { 47 n=get_num();m=get_num(); 48 memset(head,-1,sizeof(head)); 49 int u,v; 50 for(int i=1;i<=m;++i) { 51 u=get_num();v=get_num(); 52 insert(u,v);insert(v,u); //无向图 53 } 54 bfs(); 55 for(int i=1;i<=n;++i) { 56 if(i!=1) putchar(‘\n‘); 57 printf("%d",cnt[i]); 58 } 59 return 0; 60 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9556380.html
