最短路计数

题目描述

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

输入描述

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

输出描述

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

样例输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
样例输出
1
1
1
2
4

这道题需要用到广搜,与动态规划结合求解

它求的是最短路,没有边权,所以说这里我们走到当前边的路径长度,就设为前一个点的最短路径加1,其实也就是求边权都是1的图的最短路径

接着就是说统计路径数量,我们画个图来分析一下

所以说,当前点的最短路径总数,就是所有入边最短路径总数之和

剩下的步骤,就和广搜没什么差异了

#include<bits/stdc++.h>
#define mod 100003
using namespace std;
const int N=5e6+5;
vector<int>a[N];
int n,m;
int dis[N];
int vis[N];
int dp[N];
queue<int>q;
void bfs(){
	dis[1]=0;//1号点走到1号点只要零步
	dp[1]=1;//走到底一个点只有一种
	q.push(1);//起点入队
	vis[1]=1;//标记起点
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<a[x].size();i++){//找出边
			int v=a[x][i];
			if(vis[v]==0){
				vis[v]=1;
				dis[v]=dis[x]+1;//当前点的最短路径长度
				q.push(v);
			}
			if(dis[v]==dis[x]+1){
				dp[v]=(dp[x]+dp[v])%mod;//状态转移
			}
		}
	}
}
signed main(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);//无向图,所以要反着再入一次
	}
	bfs();
	for(int i=1;i<=n;i++)printf("%d\n",dp[i]);
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/522195.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

机器学习周记(第三十三周:文献阅读[GWO-GART])2024.4.1~2024.4.7

目录 摘要 ABSTRACT 1 论文信息 1.1 论文标题 1.2 论文摘要 1.3 论文数据集 1.4 论文模型 2 相关知识 摘要 本周阅读了一篇使用GAT结合GRU预测PM2.5浓度的文章。论文模型为图注意力循环网络&#xff08;GART&#xff09;&#xff0c;首次提出了一种新型的多层GAT架构&…

2024-简单点-python中的多重继承mro和super的联系

在Python的多重继承中&#xff0c;super()函数的作用主要是确保父类的方法被正确地调用&#xff0c;同时避免了直接调用父类可能带来的问题&#xff0c;如方法覆盖或名称冲突。super()的使用是Python实现合作式多重继承的关键。 具体来说&#xff0c;当一个类从多个父类继承时…

HTTP 摘要认证

文章目录 一、什么是摘要认证二、工作流程三、实例演示 一、什么是摘要认证 摘要认证&#xff0c;即 Digest Access Authentication&#xff0c;是一种HTTP身份验证机制&#xff0c;用于验证用户的身份。相较于基本认证&#xff08;Basic Authentication&#xff09;使用用户名…

Qt快速入门到熟练(3.程序运行发布与设置图标)

程序运行发布 当我们执行过qt过后&#xff0c;将会在项目目录里面生成出一个debug构建目录&#xff0c;点击进去选择debug文件夹&#xff0c;就可以看到我们生成出来的可执行文件。 很显然我们的项目就叫做MyFirstWidget&#xff0c;所以生成的可执行文件在没有人为设置的情…

CLR学习

视频链接&#xff1a;《CLR十分钟》系列之CLR运行模型_哔哩哔哩_bilibili 什么是 CLR 公共语言运行时&#xff08;Common Language Runtime CLR&#xff09; 是一个可有多种编程语言使用的 运行时&#xff0c;CLR 的核心功能&#xff08;比如 内存管理&#xff0c;程序集加载…

notion的使用心得

从老石的视频知道了notion是一个很强大的管理工具&#xff1a;这就是最棒的效率软件&#xff01;如果不是&#xff0c;我倒想试试你的 | Notion使用技巧分享_哔哩哔哩_bilibili 我一时半会不能全部学会&#xff0c;但是借用大家的好模板&#xff1a;如何用5分钟搭建简洁高效的…

html5分步问卷调查表模板源码

文章目录 1.设计来源1.1 问卷调查11.2 问卷调查21.3 问卷调查31.4 问卷调查41.5 问卷调查51.6 问卷调查6 2.效果和源码2.1 完整效果2.2 源代码 源码下载 作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/137454703 html5分…

React 项目配置代码提交规范 ESLint、Pretttier、Husky、CommitLint

React 项目配置代码提交规范 ESLint、Pretttier、Husky、CommitLint 前言 团队开发的成员越来越多&#xff0c;项目都是由多个人进行开发和维护&#xff0c;每个人的代码书写习惯和风格又不尽相同&#xff0c;commit 的提交log 也是乱七八糟&#xff0c;为以后的开发和维护增…

PPT在线压缩工具推荐

有时候使用邮箱发送邮件时&#xff0c;添加的PPT、Word、PDF文档总会因为过大而转为其他类型的附件发送&#xff0c;不仅上传缓慢&#xff0c;对方查收下载时还有有效期限制&#xff0c;7天或15天后就过期再也无法下载了&#xff0c;有没有什么办法可以压缩PPT等文档&#xff0…

python3内置持久化模块shelve心得

python3内置持久化模块shelve心得 来自python官方网站的解释&#xff1a; https://docs.python.org/zh-cn/3.10/library/shelve.html 本文环境&#xff1a; Windows 10 专业版 64 位 Thonny 3.2.6 概述 内置模块 shelve 可以将任意 Python 对象&#xff08;即 https://docs…

第29篇:秒表计时器

Q&#xff1a;本期我们采用计数器来实现秒表计时器&#xff0c;循环进行0~9计时。 A&#xff1a;在数码管HEX0上循环从0到9计数&#xff0c;间隔时间为1s&#xff0c;使用计数器实现1s时间间隔。 DE2-115开发板提供了50MHz时钟&#xff0c;触发器直接以50MHz信号作为同步时钟…

C++ | Leetcode C++题解之第11题盛最多水的容器

题目&#xff1a; 题解&#xff1a; class Solution { public:int maxArea(vector<int>& height) {int l 0, r height.size() - 1;int ans 0;while (l < r) {int area min(height[l], height[r]) * (r - l);ans max(ans, area);if (height[l] < height[r…

鸿蒙实现一种仿小红书首页滑动联动效果

前言&#xff1a; DevEco Studio版本&#xff1a;4.0.0.600 效果描述&#xff1a;通过手指滑动列表&#xff0c;控制位置显示效果为&#xff1a;不论列表在什么位置下滑时下图粉色位置布局显示&#xff0c;手指上滑时下图粉色位置布局隐藏。 效果&#xff1a; 原理分析&…

简单介绍css及其代码样式

css简介 css用于前端开发&#xff0c;负责对界面进行美化。让页面更美观。 他可以改变html代码的样式&#xff0c;让html代码的网页不那么死板。 css代码格式 选择器 {属性:值; 属性:值&#xff1b;} css的模版架构 css代码放到<style>标签中。 而<style>通常是…

2024/4/7周报

文章目录 摘要Abstract文献阅读题目引言创新点Decoder-Encoder模型实验过程实验结果 深度学习LSTM变体Bidirectional LSTM&#xff08;双向LSTM&#xff09;GRUGRU代码实现 总结 摘要 用于统计机器翻译的RNN编码器-解码器学习短语表示 文中提出了一种新的神经网络模型称为RNN编…

博客评论回复03

接着之前写的&#xff0c;之前返回的数据集按道理来说渲染出来还是丑丑的&#xff0c;因此这次我看着抖音的评论样子&#xff0c;自己瞎写了一通&#xff0c;不过也算是模仿出来了虽然肯定没有抖音写的好。 类似与前面几章写的表结构 首先看看抖音评论区是怎么样的&#xff1f…

消息队列之RabbitMQ的安装配置

一&#xff0c;前言 RabbitMQ是由erlang语言开发&#xff0c;基于AMQP&#xff08;Advanced Message Queue 高级消息队列协议&#xff09;协议实现的消息队列&#xff0c;它是一种应用程序之间的通信方法&#xff0c;消息队列在分布式系统开发中应用非常广泛。点击跳转RabbitM…

前端开发学习笔记 3 (Chrome浏览器调试工具、Emmet语法、CSS复合选择器、CSS元素选择模式、CSS背景)

文章目录 Chrome浏览器调试工具Emmet语法CSS复合选择器后代选择器子选择器并集选择器伪类选择器 CSS元素选择模式元素选择模式概述CSS块标签CSS行内标签CSS行内块标签CSS元素显示模式转换 CSS背景CSS背景颜色CSS背景图片CSS背景图片平铺CSS背景图片位置CSS背景图片固定CSS背景复…

HIS系统是什么?一套前后端分离云HIS系统源码 接口技术RESTful API + WebSocket + WebService

HIS系统是什么&#xff1f;一套前后端分离云HIS系统源码 接口技术RESTful API WebSocket WebService 医院管理信息系统(全称为Hospital Information System)即HIS系统。 常规模版包括门诊管理、住院管理、药房管理、药库管理、院长查询、电子处方、物资管理、媒体管理等&…

275. 传纸条(DP)

题目描述 小渊和小轩是好朋友也是同班同学&#xff0c;他们在一起总有谈不完的话题。一次素质拓展活动中&#xff0c;班上同学安排坐成一个 m 行 n 列的矩阵&#xff0c;而小渊和小轩被安排在矩阵对角线的两端&#xff0c;因此&#xff0c;他们就无法直接交谈了。幸运的是&…