我是靠谱客的博主 感性康乃馨,最近开发中收集的这篇文章主要介绍【luogu1144】最短路计数(SPFA),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目:

我是超链接

题解:

用spfa求出最短距离之后,用递归+记忆化求出ans

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <iostream>
#define Mod 100003
#define M 2000000+5
#define N 1000000+5
using namespace std;
int nxt[M],point[M],v[M],tot,ans[N],dis[N];
bool c[N];
void addline(int x,int y)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
int dfs(int t)
{
int i;
if (ans[t]) return ans[t];
for (i=point[t];i;i=nxt[i])
if (dis[t]==dis[v[i]]+1)
ans[t]=(ans[t]+dfs(v[i]))%Mod;
return ans[t];
}
int main()
{
int n,m,i,x,y;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addline(x,y);
}
queue<int>q;
q.push(1);
memset(c,0,sizeof(c));
memset(dis,0x7f,sizeof(dis));
dis[1]=0;
for (i=1;i<=n;i++)
while (!q.empty())
{
int now=q.front(); q.pop();
for (i=point[now];i;i=nxt[i])
if (dis[v[i]]>dis[now]+1)
{
dis[v[i]]=dis[now]+1;
if (!c[v[i]])
{
c[v[i]]=true;
q.push(v[i]);
}
}
}
ans[1]=1;
for (i=1;i<=n;i++)
printf("%dn",dfs(i));
}


最后

以上就是感性康乃馨为你收集整理的【luogu1144】最短路计数(SPFA)的全部内容,希望文章能够帮你解决【luogu1144】最短路计数(SPFA)所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(40)

评论列表共有 0 条评论

立即
投稿
返回
顶部