题解：洛谷 P1144 最短路计数

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1144 最短路计数 - 洛谷

【题目描述】

给出一个N NN个顶点M MM条边的无向无权图，顶点编号为1 ∼ N 1\sim N1∼N。问从顶点1 11开始，到其他每个点的最短路有几条。

【输入】

第一行包含2 22个正整数N , M N,MN,M，为图的顶点数与边数。

接下来M MM行，每行2 22个正整数x , y x,yx,y，表示有一条连接顶点x xx和顶点y yy的边，请注意可能有自环与重边。

【输出】

共N NN行，每行一个非负整数，第i ii行输出从顶点1 11到顶点i ii有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点i ii则输出0 00。

【输入样例】

5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5

【输出样例】

1 1 1 2 4

【算法标签】

#普及plus #图的遍历-BFS

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1000005,M=2000005*2,mod=100003;intn,m;// n: 节点数，m: 边数inth[N],e[M],ne[M],idx;// 邻接表存储图intdist[N],cnt[N];// dist: 节点到起点的最短距离，cnt: 到节点的最短路径数量vector<int>ans[N];// 未使用的数组// 添加无向边voidadd(inta,intb){e[idx]=b;// 边的终点ne[idx]=h[a];// 指向a的下一条边h[a]=idx++;// 更新a的头节点}queue<int>q;// BFS队列// 广度优先搜索，计算最短路径长度和数量voidbfs(){memset(dist,-1,sizeof(dist));// 初始化距离为-1（表示未访问）q.push(1);// 从节点1开始dist[1]=0;// 起点距离为0cnt[1]=1;// 到起点的最短路径数量为1while(!q.empty())// BFS遍历{intu=q.front();// 取出队首q.pop();// 弹出队首for(inti=h[u];i!=-1;i=ne[i])// 遍历u的所有邻接点{intv=e[i];// 邻接点vif(dist[v]==-1)// 如果v未访问{dist[v]=dist[u]+1;// 更新v的距离cnt[v]=cnt[u];// 路径数量等于u的路径数量q.push(v);// v入队}elseif(dist[v]==dist[u]+1)// 如果找到另一条最短路径{cnt[v]=(cnt[v]+cnt[u])%mod;// 累加路径数量}}}}intmain(){scanf("%d%d",&n,&m);// 输入节点数和边数memset(h,-1,sizeof(h));// 初始化邻接表while(m--)// 输入所有边{intu,v;scanf("%d%d",&u,&v);add(u,v),add(v,u);// 添加无向边}bfs();// 执行BFS计算最短路径for(inti=1;i<=n;i++)// 输出每个节点的最短路径数量printf("%d\n",cnt[i]);return0;}

【运行结果】

5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5 1 1 1 2 4