【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）内容请搜索靠谱客的其他文章。