当前位置: 首页 > news >正文

【算法】最短路计数(搜索)复习

题目

给出一个 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 条边的无向无权图&#xff0c;顶点编号为 1 到 N。 问从顶点 1 开始&#xff0c;到其他每个点的最短路有几条。 输入格式 第一行包含 2 个正整数 N,M&#xff0c;为图的顶点数与边数。 接下来 M 行&#xff0c;每行两个正整数 x,y&#xff0c;表…...

html火焰文字特效

下面是代码&#xff1a; <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>HTML5火焰文字特效DEMO演示</title><link rel"stylesheet" href"css/style.css" media"screen" type&quo…...

Redis双写一致性

所有的情况都是再并发情况下存在温蒂 一、先更新数据库&#xff0c;再更新缓存场景-不推荐 当有两个线程A、B&#xff0c;同时对一条数据进行操作&#xff0c;一开始数据库和redis的数据都为1&#xff0c;当线程A去修改数据库&#xff0c;将1改为2&#xff0c;然后线程A在修改…...

html+css+javascript实现贪吃蛇游戏

文章目录 一、贪吃蛇游戏二、JavaScript三、HTML四、CSS五、热门文章 一、贪吃蛇游戏 这是一个简单的用HTML、CSS和JavaScript实现的贪吃蛇游戏示例。 HTML部分&#xff1a; <!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仿真器使用常见问题

一、 主要是驱动安装问题 有用户反应驱动安装不上&#xff0c;按照用户手册操作一直不能安装成功。 可以尝试如下步骤进行安装。 1. 双击设备管理器中无法安装或者提示有错误的430仿真器设备 选择驱动程序——更新驱动程序 选择手动安装 选择从电脑设备驱动列表中安装 弹出下…...

芯驰E3340软件编译以及更新步骤

打开已有工程File->Open Solution: 东南项目&#xff1a;e3340\boards\e3_324_ref_display\proj\jetour-t1n-fl3\sf\SES 编译&#xff1a;build->build sf 增加头文件和宏定义&#xff1a; 编译完成sf后&#xff0c;进行编译bootloader 东南项目&#xff1a;e3340\boa…...

HCIA——18实验:NAT

学习目标&#xff1a; NAT 学习内容&#xff1a; NAT 1.要求——基本的 2.模型 3.IP分配、规划、优化 1&#xff09;思路 R2为ISP路由器&#xff0c;其上只能配置ip地址&#xff0c;不得冉进行其他的任何配置—ospf配置 认证 、汇总、沉默接口、加快收敛、缺省路由 PC1-PC2…...

在VBA中使用SQL

VBA在处理大量的数据/计算时如果使用常规方法会比较慢,因此需要对其进行性能优化以提高运行速度,一般的方法是数组计算或者sql计算。SQL计算的速度最快,限制也是最多的,数组速度其次,灵活性也更高 如果要在vba中调用sql处理数据基本可以遵循一个套路,只要修改其中的SQL语…...

vue项目中使用Element多个Form表单同时验证

一、项目需求 在项目中一个页面中需要实现多个Form表单&#xff0c;并在页面提交时需要对多个Form表单进行校验&#xff0c;多个表单都校验成功时才能提交。 二、实现效果 三、多个表单验证 注意项&#xff1a;多个form表单&#xff0c;每个表单上都设置单独的model和ref&am…...

自然语言处理--概率最大中文分词

自然语言处理附加作业--概率最大中文分词 一、理论描述 中文分词是指将中文句子或文本按照语义和语法规则进行切分成词语的过程。在中文语言中&#xff0c;词语之间没有明显的空格或标点符号来分隔&#xff0c;因此需要通过分词工具或算法来实现对中文文本的分词处理。分词的…...

k8s-基础知识(Service,NodePort,CusterIP,NameSpace,资源限制)

Service 它提供了服务程序和外部的各种组件通信的能力&#xff1a; 1 Service 有固定的IP和端口 2 Service 背后是pod在工作 Kubernetes 会给Service分配一个静态 IP 地址&#xff0c;Service自动管理、维护后面动态变化的 Pod 集合&#xff0c;当客户端访问 Service&#xff…...

【腾讯云】您使用的腾讯云服务存在违规信息,请尽快处理

收到【腾讯云】您使用的腾讯云服务存在违规信息&#xff0c;请尽快处理&#xff0c;如何解决&#xff1f;在腾讯云服务器部署网站提示网站有违规信息如何处理&#xff1f;腾讯云百科txybk告诉各位站长&#xff0c;在腾讯网址安全中心申诉&#xff0c;申诉通过后截图上传给腾讯云…...

深度学习 Day27——J6ResNeXt-50实战解析

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制&#x1f680; 文章来源&#xff1a;K同学的学习圈子 文章目录 前言1 我的环境2 pytorch实现DenseNet算法2.1 前期准备2.1.1 引入库2.1.2 设…...

【力扣 50】Pow(x, n) C++题解(数学+递归+快速幂)

实现 pow(x, n) &#xff0c;即计算 x 的整数 n 次幂函数&#xff08;即&#xff0c;xn &#xff09;。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1024.00000 示例 2&#xff1a; 输入&#xff1a;x 2.10000, n 3 输出&#xff1a;9.26100 …...

速盾:服务器接入CDN后上传图片失败的解决方案

本文将探讨当服务器接入CDN后&#xff0c;上传图片失败的常见原因&#xff0c;并提供解决方案以解决这些问题。同时&#xff0c;我们还将附上一些相关的问题和解答&#xff0c;让读者更好地理解和应对这些挑战。 随着互联网的持续发展&#xff0c;网站的性能和速度对于用户体验…...

LabVIEW高级CAN通信系统

LabVIEW高级CAN通信系统 在现代卫星通信和数据处理领域&#xff0c;精确的数据管理和控制系统是至关重要的。设计了一个基于LabVIEW的CAN通信系统&#xff0c;它结合了FPGA技术和LabVIEW软件&#xff0c;主要应用于模拟卫星平台的数据交换。这个系统的设计不仅充分体现了FPGA在…...

FastSpeech2——TTS论文阅读

笔记地址&#xff1a;https://flowus.cn/share/1683b50b-1469-4d57-bef0-7631d39ac8f0 【FlowUs 息流】FastSpeech2 论文地址&#xff1a;lFastSpeech 2: Fast and High-Quality End-to-End Text to Speechhttps://arxiv.org/abs/2006.04558 Abstract&#xff1a; tacotron→…...

如何才能拥有比特币 - 01 ?

如何才能拥有BTC 在拥有 BTC 之前我们要先搞明白 BTC到底保存在哪里&#xff1f;我的钱是存在银行卡里的&#xff0c;那我的BTC是存在哪里的呢&#xff1f; BTC到底在哪里&#xff1f; 一句话概括&#xff0c;BTC是存储在BTC地址中&#xff0c;而且地址是公开的&#xff0c;…...

Unity | 渡鸦避难所-8 | URP 中利用 Shader 实现角色受击闪白动画

1. 效果预览 当角色受到攻击时&#xff0c;为了增加游戏的视觉效果和反馈&#xff0c;可以添加粒子等动画&#xff0c;也可以使用 Shader 实现受击闪白动画&#xff1a;受到攻击时变为白色&#xff0c;逐渐恢复为正常颜色 本游戏中设定英雄受击时播放粒子效果&#xff0c;怪物…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...