坑害我良久的一道比较水的spfa题

（传送门洛谷）

附上题目（测试数据自己看）

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

这个题可以忽略重边（大不了自己走到自己再加上一条边）。以起点1号点出发，一遍spfa找出所有的dis值，开一个ans数组存答案。如找到更小的进行松弛，更新，并且它的ans这与它的前驱节点相同。再将v的前驱节点入队再找它前驱节点的最短路。
附上代码

if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
ans[v]=ans[u];
if(!pre[v])
{
q.push(v);
pre[v]=1;
}
}

用一个pre数组维护出我们要找到那个节点的前驱节点。如果dis[u]+1==dis[v]，说明用最短路的走到u后再走到v都是1到v的一条合法最短路，所以v的答案=v的答案+u的答案。用加分原理累加起来就行了

下面是完整代码

#include<bits/stdc++.h>
#define mod 100003
using namespace std;
const int maxn=1e7;
int n,m,cnt=0;
int head[maxn],dis[maxn],ans[maxn],vis[maxn];
bool pre[maxn];
queue <int> q;
//priority_queue<int vector<int> greater<int> >q;
struct node{
int v,nex;
}e[maxn<<1];
int read()
{
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9')
{
x=10*x+ch-'0';
ch=getchar();
}
return x;
}
void init()
{
freopen("input.txt","r",stdin);
}
void add(int x,int y)
{
e[++cnt].v=y;
e[cnt].nex=head[x];
head[x]=cnt;
}
void readdata()
{
memset(dis,0x3f3f,sizeof(dis));//在memset中不要用1e7,我就在这儿调了40分钟
memset(pre,0,sizeof(pre));
memset(head,-1,sizeof(head));
n=read();
m=read();
for(int i=1;i<=m;i++)
{
int a,b;
a=read();
b=read();
add(a,b);
add(b,a);
}
}
void work()
{
dis[1]=0;
pre[1]=1;
ans[1]=1;
q.push(1);//将一号点赋予值
while(!q.empty())//先跑一边spfa找到所有dis值
{
int u=q.front();
pre[u]=0;
q.pop();
for(int i=head[u];~i;i=e[i].nex)
{
int v=e[i].v;
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
ans[v]=ans[u];//到v点的方案和到u点的方案一样
if(!pre[v])
{
q.push(v);//将前驱点入队，找到它前驱点的最短路有多少条，到时候好累加。
pre[v]=1;
}
}
else if(dis[v]==dis[u]+1)//如果距离相等，累加起来
{
ans[v]+=ans[u];
ans[v]%=mod;//不要忘了取模
}
}
}
for(int i=1;i<=n;i++)
{
printf("%dn",ans[i]);
}
}
int main()
{
//init();
readdata();
work();
return 0;
}

看来基础功夫还是任重而道远啊

最后

以上就是爱听歌春天为你收集整理的最短路计数坑害我良久的一道比较水的spfa题的全部内容，希望文章能够帮你解决最短路计数坑害我良久的一道比较水的spfa题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。