【算法】最短路计数(搜索)复习
题目
给出一个 N 个顶点 M 条边的无向无权图,顶点编号为 1 到 N。
问从顶点 1 开始,到其他每个点的最短路有几条。
输入格式
第一行包含 2 个正整数 N,M,为图的顶点数与边数。
接下来 M 行,每行两个正整数 x,y,表示有一条顶点 x 连向顶点 y 的边,请注意可能有自环与重边。
输出格式
输出 N 行,每行一个非负整数,第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路,由于答案有可能会很大,你只需要输出对 100003 取模后的结果即可。
如果无法到达顶点 i 则输出 0。
数据范围
1≤N≤1e5
1≤M≤2e5
输入样例:
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出样例:
1
1
1
2
4
思路
变量介绍:

从点1出发,开始搜索设每条边的长度为1。
=========================================================================
如果从点 t 到达点 u 时,所走的路径长度小于dist[ u ],则进行

将点 u 的cnt[ u ] 更新为cnt[ t ],dist[ u ] 更新为 dist[ t ] + 1。
=========================================================================
如果从点 t 到达点 u 时,所走的路径长度等于 dist[ u ],则进行

将cnt[t] 加到 cnt[u] 上面。
=========================================================================
如果从点 t 到达点 u 时,所走的路径长度大于 dist[ u ],则不进行任何操作。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 100100, M = 4 * N;
int n,m;
int h[N],ne[M],e[M],idx;
int dist[N],cnt[N];
bool st[N];void add(int a,int b)
{ne[idx] = h[a],e[idx] = b,h[a] = idx ++;
}void bfs()
{memset(dist,0x3f,sizeof dist);queue<int> q;cnt[1] = 1;dist[1] = 0;q.push(1);st[1] = true;while(!q.empty()){int t = q.front();st[t] = false;q.pop();for(int i = h[t]; ~i; i = ne[i]){int u = e[i];if(dist[u] > dist[t] + 1){dist[u] = dist[t] + 1;cnt[u] = cnt[t];cnt[u] %= 100003;if(!st[u]) q.push(u);}else if(dist[u] == dist[t] + 1){cnt[u] += cnt[t];cnt[u] %= 100003;}}}
}int main()
{cin >> n >> m;memset(h,-1,sizeof h);while(m --){int a,b;cin >> a >> b;add(a,b);add(b,a);}bfs();for(int i = 1; i <= n; i ++) printf("%d\n",cnt[i]);return 0;
}
| 难度:中等 |
| 时/空限制:1s / 64MB |
| 总通过数:6250 |
| 总尝试数:11237 |
| 来源:《信息学奥赛一本通》 |
| 算法标签 最短路 方案数 |
题目来自: 1134. 最短路计数 - AcWing题库
相关文章:
【算法】最短路计数(搜索)复习
题目 给出一个 N 个顶点 M 条边的无向无权图,顶点编号为 1 到 N。 问从顶点 1 开始,到其他每个点的最短路有几条。 输入格式 第一行包含 2 个正整数 N,M,为图的顶点数与边数。 接下来 M 行,每行两个正整数 x,y,表…...
html火焰文字特效
下面是代码: <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>HTML5火焰文字特效DEMO演示</title><link rel"stylesheet" href"css/style.css" media"screen" type&quo…...
Redis双写一致性
所有的情况都是再并发情况下存在温蒂 一、先更新数据库,再更新缓存场景-不推荐 当有两个线程A、B,同时对一条数据进行操作,一开始数据库和redis的数据都为1,当线程A去修改数据库,将1改为2,然后线程A在修改…...
html+css+javascript实现贪吃蛇游戏
文章目录 一、贪吃蛇游戏二、JavaScript三、HTML四、CSS五、热门文章 一、贪吃蛇游戏 这是一个简单的用HTML、CSS和JavaScript实现的贪吃蛇游戏示例。 HTML部分: <!DOCTYPE html> <html> <head><title>贪吃蛇游戏</title><styl…...
【K8S】Kubernetes 中滚动发布由浅入深实战
目录 一、Kubernetes中滚动发布的需求背景1.1 滚动发布1.2 滚动发布、蓝绿发布、金丝雀发布的区别 二、Kubernetes中实现滚动发布2.1 定义Kubernetes中的版本2.2 创建 Deployment 资源对象2.2.1 在 Yaml 中定义 Deployment 资源对象2.2.2 执行命令创建 Deployment 资源对象 三、…...
MSP430仿真器使用常见问题
一、 主要是驱动安装问题 有用户反应驱动安装不上,按照用户手册操作一直不能安装成功。 可以尝试如下步骤进行安装。 1. 双击设备管理器中无法安装或者提示有错误的430仿真器设备 选择驱动程序——更新驱动程序 选择手动安装 选择从电脑设备驱动列表中安装 弹出下…...
芯驰E3340软件编译以及更新步骤
打开已有工程File->Open Solution: 东南项目:e3340\boards\e3_324_ref_display\proj\jetour-t1n-fl3\sf\SES 编译:build->build sf 增加头文件和宏定义: 编译完成sf后,进行编译bootloader 东南项目:e3340\boa…...
HCIA——18实验:NAT
学习目标: NAT 学习内容: NAT 1.要求——基本的 2.模型 3.IP分配、规划、优化 1)思路 R2为ISP路由器,其上只能配置ip地址,不得冉进行其他的任何配置—ospf配置 认证 、汇总、沉默接口、加快收敛、缺省路由 PC1-PC2…...
在VBA中使用SQL
VBA在处理大量的数据/计算时如果使用常规方法会比较慢,因此需要对其进行性能优化以提高运行速度,一般的方法是数组计算或者sql计算。SQL计算的速度最快,限制也是最多的,数组速度其次,灵活性也更高 如果要在vba中调用sql处理数据基本可以遵循一个套路,只要修改其中的SQL语…...
vue项目中使用Element多个Form表单同时验证
一、项目需求 在项目中一个页面中需要实现多个Form表单,并在页面提交时需要对多个Form表单进行校验,多个表单都校验成功时才能提交。 二、实现效果 三、多个表单验证 注意项:多个form表单,每个表单上都设置单独的model和ref&am…...
自然语言处理--概率最大中文分词
自然语言处理附加作业--概率最大中文分词 一、理论描述 中文分词是指将中文句子或文本按照语义和语法规则进行切分成词语的过程。在中文语言中,词语之间没有明显的空格或标点符号来分隔,因此需要通过分词工具或算法来实现对中文文本的分词处理。分词的…...
k8s-基础知识(Service,NodePort,CusterIP,NameSpace,资源限制)
Service 它提供了服务程序和外部的各种组件通信的能力: 1 Service 有固定的IP和端口 2 Service 背后是pod在工作 Kubernetes 会给Service分配一个静态 IP 地址,Service自动管理、维护后面动态变化的 Pod 集合,当客户端访问 Serviceÿ…...
【腾讯云】您使用的腾讯云服务存在违规信息,请尽快处理
收到【腾讯云】您使用的腾讯云服务存在违规信息,请尽快处理,如何解决?在腾讯云服务器部署网站提示网站有违规信息如何处理?腾讯云百科txybk告诉各位站长,在腾讯网址安全中心申诉,申诉通过后截图上传给腾讯云…...
深度学习 Day27——J6ResNeXt-50实战解析
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 | 接辅导、项目定制🚀 文章来源:K同学的学习圈子 文章目录 前言1 我的环境2 pytorch实现DenseNet算法2.1 前期准备2.1.1 引入库2.1.2 设…...
【力扣 50】Pow(x, n) C++题解(数学+递归+快速幂)
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。 示例 1: 输入:x 2.00000, n 10 输出:1024.00000 示例 2: 输入:x 2.10000, n 3 输出:9.26100 …...
速盾:服务器接入CDN后上传图片失败的解决方案
本文将探讨当服务器接入CDN后,上传图片失败的常见原因,并提供解决方案以解决这些问题。同时,我们还将附上一些相关的问题和解答,让读者更好地理解和应对这些挑战。 随着互联网的持续发展,网站的性能和速度对于用户体验…...
LabVIEW高级CAN通信系统
LabVIEW高级CAN通信系统 在现代卫星通信和数据处理领域,精确的数据管理和控制系统是至关重要的。设计了一个基于LabVIEW的CAN通信系统,它结合了FPGA技术和LabVIEW软件,主要应用于模拟卫星平台的数据交换。这个系统的设计不仅充分体现了FPGA在…...
FastSpeech2——TTS论文阅读
笔记地址:https://flowus.cn/share/1683b50b-1469-4d57-bef0-7631d39ac8f0 【FlowUs 息流】FastSpeech2 论文地址:lFastSpeech 2: Fast and High-Quality End-to-End Text to Speechhttps://arxiv.org/abs/2006.04558 Abstract: tacotron→…...
如何才能拥有比特币 - 01 ?
如何才能拥有BTC 在拥有 BTC 之前我们要先搞明白 BTC到底保存在哪里?我的钱是存在银行卡里的,那我的BTC是存在哪里的呢? BTC到底在哪里? 一句话概括,BTC是存储在BTC地址中,而且地址是公开的,…...
Unity | 渡鸦避难所-8 | URP 中利用 Shader 实现角色受击闪白动画
1. 效果预览 当角色受到攻击时,为了增加游戏的视觉效果和反馈,可以添加粒子等动画,也可以使用 Shader 实现受击闪白动画:受到攻击时变为白色,逐渐恢复为正常颜色 本游戏中设定英雄受击时播放粒子效果,怪物…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
