neuq-acm预备队训练week 8 P1144 最短路计数

这篇具有很好参考价值的文章主要介绍了neuq-acm预备队训练week 8 P1144 最短路计数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

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

题目限制

neuq-acm预备队训练week 8 P1144 最短路计数,算法,数据结构,图论

输入格式

第一行包含 22 个正整数 N,M,为图的顶点数与边数。

接下来 M 行,每行 2个正整数 x,y,表示有一条由顶点 x 连向顶点 y 的边,请注意可能有自环与重边。

输出格式

共 N 行,每行一个非负整数,第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出  ans  mod  100003 后的结果即可。如果无法到达顶点 i 则输出 0。

输入输出样例

neuq-acm预备队训练week 8 P1144 最短路计数,算法,数据结构,图论

解题思路

基于图论的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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 最短路Dijkstra,spfa,图论二分图算法AYIT---ACM训练(模板版)

    最短路Dijkstra,spfa,图论二分图算法AYIT—ACM训练(模板版) A — Dijkstra B — spfa/Dijkstra C — 二分图 D — 二分图 E — 二分图 F — 二分图 G — Dijkstra H — Topsort Dijkstra算法基础模板题 💬 模板演示: 朴素版本Dijkstra: 💬 代码演示: 🚩 运行结果: spfa算法: 💬 代码演示: 🚩

    2024年02月10日
    浏览(48)
  • 【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和

    DAY16共3题: 奇♂妙拆分(简单数学) 区区区间间间(单调栈) 小AA的数列(位运算dp) 🎈 作者:Eriktse 🎈 简介:19岁,211计算机在读,现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)🚀 🎈 阅读原

    2023年04月20日
    浏览(46)
  • P1144 最短路计数

    给出一个 N N N 个顶点 M M M 条边的无向无权图,顶点编号为 1 ∼ N 1sim N 1 ∼ N 。问从顶点 1 1 1 开始,到其他每个点的最短路有几条。 第一行包含 2 2 2 个正整数 N , M N,M N , M ,为图的顶点数与边数。 接下来 M M M 行,每行 2 2 2 个正整数 x , y x,y x , y ,表示有一条由顶点 x x x 连

    2024年02月14日
    浏览(29)
  • P1144 最短路计数 题解

    给出一个 N N N 个顶点 M M M 条边的无向无权图,顶点编号为 1 ∼ N 1sim N 1 ∼ N 。问从顶点 1 1 1 开始,到其他每个点的最短路有几条。 第一行包含 2 2 2 个正整数 N , M N,M N , M ,为图的顶点数与边数。 接下来 M M M 行,每行 2 2 2 个正整数 x , y x,y x , y ,表示有一条由顶点 x x x 连

    2024年02月05日
    浏览(28)
  • 【C++---面向对象预备】

    所有书写后的代码都会在代码区,存放的是(转化后的二进制代码) 特点:共享,但只读 存放 全局变量 (函数体外的变量), 静态变量 (普通变量前面加static就是静态变量) 常量 ( 字符串常量 和const修饰的 全局常变量 ),这三种在内存种的距离比较近 特点:数据的 声明

    2024年02月09日
    浏览(21)
  • 0、C++预备知识

    C++是一种计算机高级程序设计语言,C++既可以进行C语言的过程化程序设计,又可以进行以抽象数据类型为特点的基于对象的程序设计。 C++对比C语言的特点: 与C语言的兼容性。C++与C语言完全兼容,c语言的绝大多数内容可以直接用于C++的程序设计。用C语言编写的程序可以不

    2024年01月18日
    浏览(23)
  • 论坛项目学习记录【预备篇1】

    java bean实际上时java程序中对类约定的定义规则 是一套规范,有了这套规范,方便使用和交流 所有类必须定义在包里 除非特殊原因一定要有无参构造 要实现序列化接口 所有属性需要使用getXxx和SetXxx的规则 我们之前的案例中使用的是@Bean来进行的注入 这种注入是需要编写代码的

    2024年02月07日
    浏览(23)
  • 机器学习&&深度学习——预备知识(上)

    深大的夏令营已经结束,筛选入营的保研er就筛选了1/3,280多的入营总人数里面双非只有30左右。 最终虽然凭借机试拿到offer了,但是我感受到了自己的明显短板,比如夏令营的舍友就都有一篇核心论文,甚至还有SCI一区一作的。 既然,学历和没过六级这件事在9月份之前都没

    2024年02月16日
    浏览(42)
  • 高等数学(预备知识之反函数)

    正弦函数 y = sin ⁡ x y=sin x y = sin x quad ( x ∈ [ − π 2 , π 2 ] xin[-frac{π}{2},frac{π}{2}] x ∈ [ − 2 π ​ , 2 π ​ ] )的反函数叫 反正弦函数 记作 y = arcsin ⁡ x y=arcsin x y = arcsin x , ( x ∈ [ − 1 , 1 ] xin[-1,1] x ∈ [ − 1 , 1 ] , y ∈ [ − π 2 , π 2 ] yin[-frac{π}{2},frac{π}{2}] y ∈ [ − 2 π

    2024年02月07日
    浏览(52)
  • 网络编程套接字 | 预备知识

    在之后的文章中我们将来讲解网络编程中的相关知识点,再本文中我们首先来讲解一下网络编程中的预备知识: 在IP数据包中有两个IP地址分别是源IP地址和目的IP地址,此时这里就会出现一个问题就是:如果我们光有IP地址,是无法完成通信的。有了IP地址只能够将消息发送到

    2024年02月09日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包