题源：https://www.luogu.org/problem/P1144 思路来源：https://www.luogu.org/problemnew/solution/P1144
这个解法不太好想 因为路径长度都是1，可以用BFS来解 0、这个题稍微简单一点的地方就是边权均为1，若边权不是1的话，这题就不能用。 1、广搜，一个点只入队一次。 2、核心思想：通过当前点去确定下一个点的深度（路径长度）：具体描述是，看当前点指向的所有点有没有确定过，若没确定过(book[i]==0)，那入队并确定深度，此时因为第一次入队，路径条数就等于上一个点的最短路条数。若确定过，说明不是第一次入队，就判断当前点是不是比下一个点浅一层，然后再加上当前点的最短路数量即可。 为什么这么做？首先因为保证了“下一个点”是“当前点”可达的，所以每当当前点去扩下一个点的时候，都已经保证了是可达的，其次再保证当前点是下一个点的上一层点即可！
核心代码：
if(book[v]==0){//若该点没来过 book是防止一个点多次入队 dis[v]=dis[u]+1;//取先入队的！！！ book[v]=1; q.push(v); } if(dis[v]==dis[u]+1){//防止同级的影响 cnt[v]=(cnt[v]+cnt[u])%mod;//用父点来更新当前点 } #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define MID (t[k].l+t[k].r)>>1 #define cl(a,b) memset(a,b,sizeof(a)) #define mod 100003 using namespace std; const int maxn=1e6+10; int n,m,num; struct Side{ int v,next; }side[maxn]; int head[maxn],dis[maxn],cnt[maxn],book[maxn]; queue<int> q; void add(int u,int v){ num++; side[num].v=v; side[num].next=head[u]; head[u]=num; } void init(){ num=0; cl(head,-1); cl(cnt,0); cl(dis,inf); dis[1]=0; } int main(){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } q.push(1); book[1]=1; cnt[1]=1;//初始化为1 while(!q.empty()){ int u=q.front(); q.pop(); //book[u]=0;不行 广搜！ 这里只入队一次！！！ for(int i=head[u];i!=-1;i=side[i].next){ int v=side[i].v; if(book[v]==0){//若该点没来过 book是防止一个点多次入队 dis[v]=dis[u]+1;//取先入队的！！！ book[v]=1; q.push(v); } if(dis[v]==dis[u]+1){//防止同级的影响 cnt[v]=(cnt[v]+cnt[u])%mod;//用父点来更新当前点 } } } for(int i=1;i<=n;i++){ printf("%d\n",cnt[i]); } return 0; }这个解法2的核心代码和下面的解法3一样。其他题解讲的很清楚了，就是：出现等长的最短路就加上，出现更小的就赋值。
if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; cnt[v]=cnt[u]; temp.id=v; temp.dis=dis[v]; q.push(temp); }else if(dis[v]==dis[u]+1){ cnt[v]+=cnt[u]; cnt[v]%=mod;//刚开始写错了TAT }AC代码如下：
#include<iostream>//dijkstra堆优化 #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define MID (t[k].l+t[k].r)>>1 #define cl(a,b) memset(a,b,sizeof(a)) #define mod 100003 using namespace std; const int maxn=1e6+10; int n,m,num; struct Side{ int v,next; }side[maxn]; int head[maxn],dis[maxn],cnt[maxn],book[maxn]; struct node{ int id,dis; }; bool operator<(node x,node y){ return x.dis>y.dis; } priority_queue<node> q; void add(int u,int v){ num++; side[num].v=v; side[num].next=head[u]; head[u]=num; } void init(){ num=0; cl(head,-1); cl(cnt,0); cl(dis,inf); dis[1]=0; } int main(){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } node temp; temp.id=1; temp.dis=0; q.push(temp); cnt[1]=1;//初始化为1 while(!q.empty()){ int u=q.top().id; q.pop(); if(book[u]) continue; book[u]=1; for(int i=head[u];i!=-1;i=side[i].next){ int v=side[i].v; if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; cnt[v]=cnt[u]; //if(!book[v]){//这里不需要这个 尽管入列 用的时候只用最小的 temp.id=v; temp.dis=dis[v]; q.push(temp); //book[v]=1;这里不加入队列 //} }else if(dis[v]==dis[u]+1){ cnt[v]+=cnt[u]; cnt[v]%=mod;//刚开始写错了TAT } } } for(int i=1;i<=n;i++){ printf("%d\n",cnt[i]); } return 0; }AC代码如下 其实不要说为什么之际上代码 其实解题方法就是当前算法多一个cnt数组记录最小条数即可
#include<iostream>//spfa算法！！！ #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #define ll long long #define inf 0x3f3f3f3f #define MID (t[k].l+t[k].r)>>1 #define cl(a,b) memset(a,b,sizeof(a)) #define mod 100003 using namespace std; const int maxn=1e6+10; int n,m,num; struct Side{ int v,next; }side[maxn]; int head[maxn],dis[maxn],cnt[maxn],book[maxn]; queue<int> q; void add(int u,int v){ num++; side[num].v=v; side[num].next=head[u]; head[u]=num; } void init(){ num=0; cl(head,-1); cl(cnt,0); cl(dis,inf); dis[1]=0; } int main(){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } q.push(1); book[1]=1; cnt[1]=1;//初始化为1 while(!q.empty()){ int u=q.front(); q.pop(); book[u]=0; for(int i=head[u];i!=-1;i=side[i].next){ int v=side[i].v; if(dis[v]>dis[u]+1){ dis[v]=dis[u]+1; cnt[v]=cnt[u]; if(book[v]==0){ q.push(v); } }else if(dis[v]==dis[u]+1){ cnt[v]+=cnt[u]; cnt[v]%=mod; } } } for(int i=1;i<=n;i++){ printf("%d\n",cnt[i]); } return 0; }题目描述 给出一个 NN N个顶点 MM M条边的无向无权图，顶点编号为 1−N1-N 1−N。问从顶点 11 1开始，到其他每个点的最短路有几条。 输入格式 第一行包含 22 2个正整数 N,MN,M N,M，为图的顶点数与边数。 接下来 MM M行，每行 22 2个正整数 x,yx,y x,y，表示有一条顶点 xx x连向顶点 yy y的边，请注意可能有自环与重边。 输出格式 共 NN N行，每行一个非负整数，第 ii i行输出从顶点 11 1到顶点 ii i有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ansmod100003 ans \bmod 100003 ansmod100003后的结果即可。如果无法到达顶点 ii i则输出 00 0。 输入输出样例 输入 #1 复制 5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5 输出 #1 复制 1 1 1 2 4 说明/提示 11 1到 55 5的最短路有 44 4条，分别为 22 2条 1−2−4−51-2-4-5 1−2−4−5和 22 2条 1−3−4−51-3-4-5 1−3−4−5（由于 4−54-5 4−5的边有 22 2条）。 对于 20 % 20%的数据， N≤100N ≤ 100 N≤100； 对于 60`% 60%的数据， N≤1000N ≤ 1000 N≤1000； 对于 1000% 100%的数据， N<=1000000,M<=2000000N<=1000000,M<=2000000 N<=1000000,M<=2000000。
