【算法】最优乘车——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混合现实教学系统在汽车检修与维护课堂教学中的应用
传统的汽车检修与维护课堂教学主要依赖教师口头讲解和黑板演示,这种方式存在一定的局限性。首先,对于一些复杂的机械结构和操作过程,教师难以生动形象地展示给学生。其次,学生无法直接观察到实际操作中的细节和注意事项࿰…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...
CSS3相关知识点
CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...
