【算法】最优乘车——bfs(stringsteam的实际应用,getline实际应用)
题目
H 城是一个旅游胜地,每年都有成千上万的人前来观光。
为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴士线路。
每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,最终到达终点巴士站。
一名旅客最近到 H 城旅游,他很想去 S 公园游玩,但如果从他所在的饭店没有一路巴士可以直接到达 S 公园,则他可能要先乘某一路巴士坐几站,再下来换乘同一站台的另一路巴士,这样换乘几次后到达 S 公园。
现在用整数 1,2,…N 给 H 城的所有的巴士站编号,约定这名旅客所在饭店的巴士站编号为 1,S 公园巴士站的编号为 N。
写一个程序,帮助这名旅客寻找一个最优乘车方案,使他在从饭店乘车到 S 公园的过程中换乘的次数最少。
输入格式
第一行有两个数字 M 和 N,表示开通了 M 条单程巴士线路,总共有 N 个车站。
从第二行到第 M+1 行依次给出了第 1 条到第 M 条巴士线路的信息,其中第 i+1 行给出的是第 i 条巴士线路的信息,从左至右按运行顺序依次给出了该线路上的所有站号,相邻两个站号之间用一个空格隔开。
输出格式
共一行,如果无法乘巴士从饭店到达 S 公园,则输出 NO,否则输出最少换乘次数,换乘次数为 0 表示不需换车即可到达。
数据范围
1 ≤ M ≤ 100
2 ≤ N ≤ 500
输入样例:
3 7
6 7
4 7 3 6
2 1 3 5
输出样例:
2
思路
假设一条公交路线为1 -> 2 -> 3 -> 4则,从1号点乘车可以到达2,3,4,从2号点出发可以到3,4,从3号点出发可以到4。
我们可以建立单向边1 -> 2,1 -> 3,1 -> 4,2 -> 3,2 -> 4,3 -> 4,然后进行宽度搜索就可以得到换成最少次数。
本题难点在于输入,具体输入方法见代码。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int m,n;
int stop[N];
bool g[N][N];
int dist[N];
bool st[N];void bfs()
{memset(dist,0x3f3f3f3f,sizeof(dist));dist[1] = 0;queue<int> heap;heap.push(1);while(!heap.empty()){int t = heap.front();heap.pop();for(int i = 1; i <= n; i ++){if(g[t][i] && dist[i] > dist[t] + 1){dist[i] = dist[t] + 1;heap.push(i);}}}
}int main()
{cin >> m >> n;string line;getline(cin,line);while(m --){getline(cin,line);stringstream ssin(line);int cnt = 0,p;while(ssin >> p) stop[cnt ++] = p;for(int i = 0; i < cnt; i ++)for(int j = i + 1; j < cnt; j ++)g[stop[i]][stop[j]] = true;}bfs();if(dist[n] == 0x3f3f3f3f) cout << "NO" << endl;else cout << max(dist[n] - 1,0) << endl;return 0;
}
标签
| 难度:中等 |
| 时/空限制:1s / 64MB |
| 来源:NOI1997 |
| 算法标签:单源最短路 |
相关文章:
【算法】最优乘车——bfs(stringsteam的实际应用,getline实际应用)
题目 H 城是一个旅游胜地,每年都有成千上万的人前来观光。 为方便游客,巴士公司在各个旅游景点及宾馆,饭店等地都设置了巴士站并开通了一些单程巴士线路。 每条单程巴士线路从某个巴士站出发,依次途经若干个巴士站,…...
『亚马逊云科技产品测评』活动征文|通过lightsail一键搭建Drupal VS 手动部署
『亚马逊云科技产品测评』活动征文|通过lightsail一键搭建Drupal 提示:授权声明:本篇文章授权活动官方亚马逊云科技文章转发、改写权,包括不限于在 Developer Centre, 知乎,自媒体平台,第三方开发者媒体等亚…...
使用 VuePress 和 Vercel 打造个人技术博客:实现自动化部署
什么是VuePress? 以下是VuePress官方文档的介绍:VuePress 是一个以 Markdown 为中心的静态网站生成器。你可以使用 Markdown 来书写内容(如文档、博客等),然后 VuePress 会帮助你生成一个静态网站来展示它们。VuePress 诞生的初…...
Re50:读论文 Large Language Models Struggle to Learn Long-Tail Knowledge
诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文名称:Large Language Models Struggle to Learn Long-Tail Knowledge ArXiv网址:https://arxiv.org/abs/2211.08411 官方GitHub项目(代码和实体)…...
Spring IOC - Bean的生命周期之依赖注入
在Spring启动流程中,创建的factoryBean是DefaultListableBeanFactory,其类图如下所示: 可以看到其直接父类是AbstractAutoireCapableBeanFactory,他主要负责完成Bean的自动装配和创建工作。 具体来说,AbstractAutowire…...
Android Termux安装MySQL,内网穿透实现公网远程访问
文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备,尽管最初并非设计为服务器,但是随着技术的进步我们可以将Android配置为生产力工具,变成一个随身…...
OpenCV快速入门:像素操作和图像变换
文章目录 前言1. 像素操作1.1 像素统计1.2 两个图像之间的操作1.2.1 图像加法操作1.2.3 图像加权混合 1.3 二值化1.4 LUT(查找表)1.4.1 查找表原理1.4.2 代码演示 2 图像变换2.1 旋转操作2.1.1 旋转的基本原理2.1.2 代码实现 2.2 缩放操作2.3 平移操作2.…...
Django 路由配置(二)
一、路由 就是根据用户请求的URL链接来判断对应的出来程序,并返回处理结果,也是就是URL和django的视图建立映射关系. 二、Django请求页面的步骤 1、首先Django确定要使用的根URLconf模块,通过ROOT_URLCONF来设置,在settings.py配置…...
电子学会C/C++编程等级考试2022年06月(一级)真题解析
C/C++等级考试(1~8级)全部真题・点这里 第1题:倒序输出 依次输入4个整数a、b、c、d,将他们倒序输出,即依次输出d、c、b、a这4个数。 时间限制:1000 内存限制:65536输入 一行4个整数a、b、c、d,以空格分隔。 0 < a,b,c,d < 108输出 一行4个整数d、c、b、a,整数之…...
【C++】使用std::vector()函数实现矩阵的加、减、点乘、点除等运算
本文通过vector()函数表示矩阵的形式,对 加、减、点乘、点除等运算进行编码和运行,相应结果如下文所述。 #include <iostream> #include <vector>using namespace std;// 矩阵加法 vector<vector<int>> …...
【python】直方图正则化详解和示例
直方图正则化(Histogram Normalization)是一种图像增强技术,目的是改变图像的直方图以改善图像的质量。具体来说,它通过将图像的直方图调整为指定的形状,以增强图像的对比度和亮度。 直方图正则化的基本步骤如下&…...
c语言:矩阵交换
题目: 代码和思路: #define _CRT_SECURE_NO_WARNINGS #include<stdio.h>int main() {int n 0;int m 0;int arr[10][10] { 0 }; // 输入行和列scanf("%d%d", &n, &m);int i 0;int j 0;//读取数组for (i 0; i < n; i)…...
【论文阅读】基于隐蔽带宽的汽车控制网络鲁棒认证(一)
文章目录 Abstract第一章 引言1.1 问题陈述1.2 研究假设1.3 贡献1.4 大纲 第二章 背景和相关工作2.1 CAN安全威胁2.1.1 CAN协议设计2.1.2 CAN网络攻击2.1.3 CAN应用攻击 2.2 可信执行2.2.1 软件认证2.2.2 消息身份认证2.2.3 可信执行环境2.2.4 Sancus2.2.5 VulCAN 2.3 侧信道攻…...
暖阳脚本_ 将Agent技术的灵活性引入RPA,清华等发布自动化智能体ProAgent
RPA暖阳脚本 近日,来自清华大学的研究人员联合面壁智能、中国人民大学、MIT、CMU 等机构共同发布了新一代流程自动化范式 “智能体流程自动化” Agentic Process Automation(APA),结合大模型智能体帮助人类进行工作流构建&#x…...
JUnit 单元自动化
一、Junit 是什么? Junit 是 Java 中用于单元测试的框架。使用 Junit 能让我们快速高效的完成单元测试。 自动化测试:JUnit提供了自动化测试的能力,开发人员可以编写一次测试用例,然后通过简单的命令或集成到持续集成工具中进行…...
Vue3 源码解读系列(十一)——插槽 slot
slot 插槽的实现实际上就是一种 延时渲染,把父组件中编写的插槽内容保存到一个对象上,并且把具体渲染 DOM 的代码用函数的方式封装,然后在子组件渲染的时候,根据插槽名在对象中找到对应的函数,然后执行这些函数做真正的…...
[github初学者教程] 分支管理-以及问题解决
作者:20岁爱吃必胜客(坤制作人),近十年开发经验, 跨域学习者,目前于新西兰奥克兰大学攻读IT硕士学位。荣誉:阿里云博客专家认证、腾讯开发者社区优质创作者,在CTF省赛校赛多次取得好成绩。跨领域…...
见面礼——图论
给定一个 n 个点 n 条边的无向图,你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案,使得删去 (x,y) 后图变成一棵树,且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。 Input 输入的第一行一个整数…...
【论文阅读】SPARK:针对视觉跟踪的空间感知在线增量攻击
SPARK: Spatial-Aware Online Incremental Attack Against Visual Tracking introduction 在本文中,我们确定了视觉跟踪对抗性攻击的一个新任务:在线生成难以察觉的扰动,误导跟踪器沿着不正确的(无目标攻击,UA&#x…...
MR混合现实教学系统在汽车检修与维护课堂教学中的应用
传统的汽车检修与维护课堂教学主要依赖教师口头讲解和黑板演示,这种方式存在一定的局限性。首先,对于一些复杂的机械结构和操作过程,教师难以生动形象地展示给学生。其次,学生无法直接观察到实际操作中的细节和注意事项࿰…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
