题目描述
给出一个 N 个顶点 M条边的无向无权图,顶点编号为 1∼N。问从顶点 1 开始,到其他每个点的最短路有几条。
题目限制
输入格式
第一行包含 22 个正整数 N,M,为图的顶点数与边数。
接下来 M 行,每行 2个正整数 x,y,表示有一条由顶点 x 连向顶点 y 的边,请注意可能有自环与重边。
输出格式
共 N 行,每行一个非负整数,第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出 ans mod 100003 后的结果即可。如果无法到达顶点 i 则输出 0。
输入输出样例
文章来源:https://www.toymoban.com/news/detail-759806.html
解题思路
基于图论的DFS,我们可以通过 记忆化搜索 或者 DP 进行优化。我们这里选择使用DP。用SPFA预处理跑一边最短路文章来源地址https://www.toymoban.com/news/detail-759806.html
AC代码
#include <bits/stdc++.h>
#define inf 0x7FFFFFFF
using namespace std;
#define Max 2000005
#define mod 100003
int n,m,head[Max],cnt,dis[Max],dp[Max];
bool inq[Max],vis[Max];
struct edge{
int to,nxt;
}e[Max];
void SPFA();
void DP();
void add(int u,int v);
int main()
{
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
SPFA();
DP();
for(int i=1;i<=n;++i) printf("%d\n",dp[i]);
return 0;
}
void add(int u,int v)
{
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void SPFA()
{
priority_queue <pair<int,int> > q;
for(int i=2 ;i<=n;++i) dis[i] = inf;
q.push(make_pair(0,1));
inq[1] = 1;
while(!q.empty())
{
int now = q.top().second;
q.pop();
inq[now] = 0;
for(int i = head[now];i;i = e[i].nxt)
{
int to = e[i].to;
if(dis[to] > dis[now] + 1)
{
dis[to] = dis[now] + 1;
q.push(make_pair(-dis[to],to));
inq[to] = 1;
}
}
}
}
void DP()
{
memset(vis,0,sizeof(vis));
queue <int> q;
q.push(1);dp[1]=1;vis[1]=1;dis[1]=0;
while(!q.empty())
{
int now = q.front();q.pop();
for(int i=head[now];i;i=e[i].nxt)
{
int to = e[i].to;
if(dis[to] == dis[now] + 1)
{
dp[to] += dp[now];
dp[to] %= mod;
if(!vis[to])
q.push(to),vis[to] = 1;
}
}
}
}
到了这里,关于neuq-acm预备队训练week 8 P1144 最短路计数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!