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

AcWing 920. 最优乘车

题面

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,
1≤N≤500

解题思路

对每条线路来说,从某个点a到其能到的点b都不用换乘,所以可以建一条从a至b边权为1的边,表示从a至b乘坐的车次。将所有这样的边处理完后可以 d[S] 即为总共乘车的次数,换成次数则为max( 0 , d[S] - 1 ) 。

由于每条线路上点的个数不同,使用sstream处理输入数据

#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
const int N = 510 ; int g[N][N] , st[N] , d[N] ; int n , m ; 
int tmp[N] ;
int q[N] ; void bfs(){int hh = 0  ,tt = 0 ; memset(d,0x3f,sizeof(d)) ; d[1] = 0 ; q[0] = 1 ;st[1] = 1 ; while( hh <= tt ) {int t = q[hh++] ; for(int i = 1 ; i <= n ; i ++ ) {if( g[t][i] && !st[i] && d[i] > d[t] + 1 ) {d[i] = d[t] + 1 ; st[i] = 1 ;q[++tt] = i ; }}}
}
int main(){cin >> m >> n ; getchar() ; //处理回车while(m--){string s ; getline(cin,s) ; stringstream ssin(s) ; int cnt = 0 , p ; while( ssin >> p ) {tmp[cnt++] = p ; }for(int i = 0 ; i < cnt ; i ++ ) {for(int j = i + 1 ; j < cnt ; j ++ ) {g[tmp[i]][tmp[j]] = 1 ; }}}bfs() ; if( d[n] == 0x3f3f3f3f ) puts("NO") ; else cout << max( 0 , d[n] - 1 ) << endl ;  return 0 ; 
}

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

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

OpenLayers源码解析8 ol/source/TileWMS.js

ol/source/TileWMS.js父类 ol/source/TileImage-TileImage 主要功能 WMS服务提供的底图图层源。 参数&#xff1a;TileWMS({}) 参数类型说明paramsObject.<string, *>至少需要LAYER参数。STYLE默认是’VERSION默认是‘1.3.0’WIDTH&#xff0c;HEIGHT&#xff0c;BB…...

代码混淆之class-winter

郑重声明 class-winter是本人在学习完class-final(v1.1.9)后&#xff0c;仿照class-final进行编写的&#xff0c;整体思路与class-final一致&#xff0c;代码部分(约20%~30%)复用了class-final中的代码。可将class-winter看作是class-fianl的一个分支。 功能与特性 支持war加…...

百度、阿里、滴滴、新浪的面试心经总结,看这一篇就够了

直击面试 反正我是带着这些问题往下读的 说一下 JVM 运行时数据区吧&#xff0c;都有哪些区&#xff1f;分别是干什么的&#xff1f;Java 8 的内存分代改进举例栈溢出的情况&#xff1f;调整栈大小&#xff0c;就能保存不出现溢出吗&#xff1f;分配的栈内存越大越好吗&#…...

Nginx 配置二级域名(腾讯云)

根域名已被个人主站占用&#xff0c;想把做过的项目部署到二级域名&#xff0c;特此记录。 一、环境说明 系统&#xff1a; CentOS7.6 应用服务器&#xff1a;Nginx 1.16.1、Tomcat 9.0 安全组已开放端口&#xff1a; 22、80、443、3389 二、解析二级域名并申请 SSL 证书&a…...

星界矿池引领区块链挖矿新时代

近年来&#xff0c;区块链技术和产业在全球范围内快速发展&#xff0c;应用已延伸到数字金融、物联网、智能制造、供应链管理、数字资产交易等多个领域&#xff0c;即使目前与区块链相关的项目层出不穷&#xff0c;但还是暴露出了许多问题。 就拿区块链挖矿产业链来说&#xf…...

牛客网论坛最具争议的Java面试成神笔记,GitHub已下载量已过百万

程序员内部一直流传这一句话&#xff1a; 面试看牛客 刷题看力扣 牛客网作为国内最牛的程序员面试网站&#xff0c;一直在程序员内部颇负盛名&#xff0c;其中用户更是卧虎藏龙! 有国内一线大厂的企业招聘 还有一些低调的互联网大牛实力就和天龙八部里的扫地僧一样&#xff0…...

JAVA大数据的第二十一天——实用类介绍

一、枚举 二、包装类 三、装箱与拆箱 四、String类 五、Random类 l六、length类 七、要点...

PAT Basic Level 1062 最简分数 解题思路及AC代码 v1.0

PAT 乙级 1062 最简分数1. 题目简述及在线测试位置2. 基本思路3. 完整AC代码1. 题目简述及在线测试位置 1.1 给定两个正分数 和 一个正整数&#xff0c;从小到大打印 以正整数为分母 并 介于两个正分数之间的最简分数。最简分数&#xff1a;分子和分母没有公约数 1.2 在线测试…...

python视频操作——python实现将视频分解为图片序列

python将视频分解为图片序列 内容参考自博客~ 详细实现代码如下&#xff1a; import cv2# 读取视频&#xff0c;方法是来自cv2库的VideoCapture cap cv2.VideoCapture("C:/Users/xxx/Desktop/sweet.mp4") # 计数 i 0 # 循环判断视频是否打开 while cap.isOpened…...

静态ip域名怎么设置?

要想在互联网上进行正常的联网使用&#xff0c;分别是&#xff1a;网站源码&#xff0c;服务器&#xff0c;域名。服务器就是用来在后台存储网站数据并支撑运行的平台&#xff0c;大家对服务器以及域名都不是很了解&#xff0c;因此&#xff0c;想要对此有了解的小伙伴&#xf…...

Python Day9函数

一函数使用步骤 &#xff08;1&#xff09;定义函数 &#xff08;2&#xff09;调用函数 如&#xff1a; 若不调用函数&#xff0c;函数内部的代码不会执行 二函数的参数的作用 三函数的返回值的作用 在函数中&#xff0c;如果需要返回结果给用户需要使用函数返…...

项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法

项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法参考文章&#xff1a; &#xff08;1&#xff09;项目部署到tomcat Root中后导致 WebApplicationContext 初始化两次的解决方法 &#xff08;2&#xff09;https://www.cnblogs.com/itrena/p/59271…...

大牛:史上最大规模SPAC交易即将落地 腾讯或成幕后赢家

美东时间周四&#xff0c;一位消息人士透露&#xff0c;亿万富翁投资者比尔•阿克曼(Bill Ackman)的空白支票公司即将完成一笔收购环球音乐集团的交易&#xff0c;这将是有史以来规模最大的特殊目的公司收购&#xff08;SPAC&#xff09;交易&#xff0c;而在环球音乐占股20%的…...

循环依赖构造器方式

文章目录构造器方式例子构造器方式 例子 Component public class TestA {private TestB testB;public TestA(TestB testB) {this.testB testB;} } Component public class TestB {private TestA testA;public TestB(TestA testA) {this.testA testA;} }TestA开始&#xff0…...

Laravel Debug mode RCE(CVE-2021-3129)漏洞复现

Laravel Debug mode RCE&#xff08;CVE-2021-3129&#xff09;漏洞复现 前言 这个之前在VNCTF2021的时候遇到过&#xff0c;当时自己只是拿着脚本直接打&#xff0c;并没有对于原理好好了解一下。最近国赛&#xff0c;还有i春秋都出现了以yii和thinkphp为背景的关于日志写ph…...

手写一个去视频水印的程序

去水印使用预览 下边和大家一起分析下做这个去水印工具的思路&#xff0c;很多人乍一听 去水印 &#xff0c;下意识地觉得是一种什么牛比的算法&#xff0c;其实这是一种假象~ 刨根问底 虽说要争口气&#xff0c;可刚开始做的时候我也真是一脸懵逼&#xff0c;因为根本不知道…...

辗转相除求最大公约数

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int a 0;int b 0;int tmp 0;scanf("%d %d", &a, &b);if (a < b){tmp a;a b;b tmp;}if (a%b ! 0){tmp a;a b;b tmp%b;}printf("%d\n", b);return 0; }...

验证排序算法是否稳定

思路&#xff1a;两个连续数字存储在数组中&#xff0c;内存地址是递增的&#xff0c;只需判断两个相同数字内存地址是否还是递增即可。 具体方案&#xff1a;需要自定义MyInteger对象&#xff0c;因为对象才可获取内存地址。此外&#xff0c;获取对象内存地址&#xff0c;需要…...

OnePlus是什么手机

OnePlus 是一家总部位于深圳的智能手机初创公司和生产商&#xff0c;成立于 2013 年 12 月。该公司声名鹊起&#xff0c;其目标是以实惠的价格提供其智能手机的旗舰级规格。OnePlus 最初仅通过邀请系统销售其智能手机&#xff0c;在该系统中&#xff0c;客户将被邀请购买智能手…...

2021年电工(中级)考试内容及电工(中级)作业模拟考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安全生产模拟考试一点通&#xff1a;2021年电工&#xff08;中级&#xff09;考试内容为正在备考电工&#xff08;中级&#xff09;操作证的学员准备的理论考试专题&#xff0c;每个月更新的电工&#xff08;中级&…...

2.1常量、变量、整型、实型和字符型

C语言的数据类型 常见数据类型所占内存的大小 数据类型32位操作系统(字节)64位操作系统(字节)char11short(unsigned short)22int(unsigned int)44float44double88long4\color{red}{4}48\color{red}{8}8long long88 常见数据类型的取值范围 数据类型最小值最大值所占字节char-…...

01_map容器_构造和赋值

map容器 自身按照key值默认排序 map中所有元素都是成对出现&#xff0c;插入数据时候要使用对组 接口&#xff1a; 判断是否为空——empty() 返回元素个数——size() 交换两个集合容器——swap() 插入——insert() (位置迭代器) 记住一种就可以了 //第一种 m.insert(…...

java与springboot 操作redis

文章目录Java&#xff08;jedis&#xff09;操作第一步导包第二步 代码Springboot 操作第一步导包&#xff1a;第二步&#xff1a; 设置yaml第三步操作&#xff1a;StringRedisTemplateRedisTemplateJava&#xff08;jedis&#xff09;操作 第一步导包 <!--引入jedis连接依…...

2021年安全员-C证复审考试及安全员-C证模拟考试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安全生产模拟考试一点通&#xff1a;安全员-C证复审考试参考答案及安全员-C证考试试题解析是安全生产模拟考试一点通题库老师及安全员-C证操作证已考过的学员汇总&#xff0c;相对有效帮助安全员-C证模拟考试题学员顺…...

centos7 yum安装使用时提示 cannot find a valid baseurl for repo:base/7/x86_64 的解决方法(亲测有效!)

一、报错原因 机子解析不了yum源,原因有三种情况&#xff1a; &#xff08;1&#xff09;电脑不能上网。请检查好网络配置&#xff0c;确认是可以上网了再看第二种情况。简单点就是ping一个公网的IP&#xff0c;如ping 114.114.114.114 如果ping不通&#xff0c;就是上不了网。…...

VG验证码识别框架2.2 免费识别验证码

该验证码服务端&#xff0c;可以免费识别常见数字、英文混合验证码&#xff1b; 功能亮点&#xff1a;通过http请求调用dll,可以识别验证码、自定义功能、可玩性极等&#xff1b; 压缩包里面有自定义功能插件案例&#xff0c;可以定制化自己需要的功能&#xff0c;需要有易语…...

计算结构体的大小

#include <stdio.h> struct mystruct1 { // 1字节对齐 4字节对齐 int a; // 4 4 char b; // 1 2(11) short c; // 2 2 }; int main(void)…...

ping localhost和本机IP区别

本机IP 下列抓包均在lo口抓取的 ping 本机IP ping localhost ping 127.0.0.1 总结 ping本机IP和127.0.0.1效果一样&#xff0c;该数据包均会被发送到lo口&#xff0c;受防火墙管控ping localhost在lo口没有抓取到数据包&#xff0c;但是实际通了&#xff0c;说明协议栈直接把…...

手写一个去视频水印的程序

去水印使用预览 下边和大家一起分析下做这个去水印工具的思路&#xff0c;很多人乍一听 去水印 &#xff0c;下意识地觉得是一种什么牛比的算法&#xff0c;其实这是一种假象~ 刨根问底 虽说要争口气&#xff0c;可刚开始做的时候我也真是一脸懵逼&#xff0c;因为根本不知道…...

导图解书-羁绊(06)《考试脑科学》

想要考试考出好成绩&#xff0c;一系列好的学习方法不可或缺。想要研究高效率的学习方法&#xff0c;首要之事是理解人脑规则。然后根据这些规则就去制定学习方法&#xff0c;尤其要注意 不要违背人脑规则&#xff0c;或者说去灵活运用人脑规则。而本书就是那个“人脑规则”。 …...

以太网之物理层

这一节来学习一下以太网的物理层&#xff0c;IEEE802.3标准就给出了以太网的物理层结构&#xff0c;如下图所示红色框内所标注的。我们可以看到物理大致可以分为&#xff1a; GMII介质无关接口、 PCS物理编码子层&#xff0c;PMA物理介质连接层&#xff0c;PMD物理介质相关层、…...

官方文档-Linux服务器集群系统(一)

转载-Linux服务器集群系统&#xff08;一&#xff09;LVS项目介绍章文嵩 (wensonglinux-vs.org)2002 年 3 月本文介绍了Linux服务器集群系统--LVS&#xff08;Linux Virtual Server&#xff09;项目的产生背景和目标&#xff0c;并描述了LVS服务器集群框架及目前提供的软件&…...

转载-lvs官方文档-LVS集群中的IP负载均衡技术

章文嵩 (wensonglinux-vs.org) 2002 年 4 月本文在分析服务器集群实现虚拟网络服务的相关技术上&#xff0c;详细描述了LVS集群中实现的三种IP负载均衡技术&#xff08;VS/NAT、VS/TUN和VS/DR&#xff09;的工作原理&#xff0c;以及它们的优缺点。1.前言在 前面文章中&#xf…...

转载-lvs官方文档-Linux服务器集群系统(二)

Linux服务器集群系统&#xff08;二&#xff09;LVS集群的体系结构章文嵩 (wensonglinux-vs.org) 2002 年 4 月本文主要介绍了LVS集群的体系结构。先给出LVS集群的通用体系结构&#xff0c;并讨论了其的设计原则和相应的特点&#xff1b;最后将LVS集群应用于建立可伸缩的Web、M…...

工作总结01

4月23日上班以来&#xff0c;我经历了无助到现在逐渐融入团队&#xff0c;在实际工作上碰见了往日没见过的各种问题&#xff0c;有数据库的&#xff0c;有shell的&#xff0c;有linux命令的&#xff0c;趁假日闲暇&#xff0c;特做整理。 一、数据库 1、Toad工具需要查sever.…...

A7_35T开发板的以太网学习

一、开发板上的原理图 从原理图上看&#xff0c;只有一个RJ45插座和一个RTL8211FD芯片&#xff0c;以及一个125Mhz的时钟信号。芯片之间的连接&#xff0c;RJ45插座会有4对差分线连接到RTL8211FD&#xff0c; 还有两个led也连接到了RTL8211FD。RTL8211的时钟输入为125Mhz&…...

Grid 布局实现九宫格图片动画

前言 &#x1f44f;Grid 布局实现九宫格&#xff0c;background-position设置背景图像起始位置&#xff0c;速速来Get吧~ &#x1f947;文末分享源代码。记得点赞关注收藏&#xff01; 1.实现效果 2.实现步骤 定义css变量&#xff1a;九宫格中每个宫格的长/宽为w&#xff0c…...

五款好玩又好用的Linux网络测试和监控工具

五款好玩又好用的Linux网络测试和监控工具【51CTO精选译文】在这篇介绍几款Linux网络测试实用工具的文章中&#xff0c;我们使用Bandwidthd、Speedometer、Nethogs、Darkstat和iperf&#xff0c;跟踪带宽使用情况和网络速度、查找网络资源消耗大户&#xff0c;以及测试性能。Ba…...

公司基础网络架构及实现

环境介绍三层楼12楼 4台二层交换机&#xff0c;4个摄像头&#xff0c;2个无线AP&#xff0c;一个门禁11楼 一台路由器&#xff0c;一台三层交换机&#xff0c;四台二层交换机&#xff0c;4个摄像头&#xff0c;2个无线AP,一个门禁&#xff0c;4台服务器&#xff0c;两台光纤…...

【正点原子FPGA连载】 第三十四章 以太网ARP测试实验-摘自【正点原子】领航者ZYNQ之FPGA开发指南_V2.0

1&#xff09;实验平台&#xff1a;正点原子领航者ZYNQ开发板 2&#xff09;平台购买地址&#xff1a;https://item.taobao.com/item.htm?&id606160108761 3&#xff09;全套实验源码手册视频下载地址&#xff1a;http://www.openedv.com/thread-301505-1-1.html 4&#x…...

【重新发布,代码开源】FPGA设计千兆以太网MAC(1)——通过MDIO接口配置与检测PHY芯片...

原创博客&#xff0c;转载请注明出处&#xff1a;【重新发布&#xff0c;代码开源】FPGA设计千兆以太网MAC&#xff08;1&#xff09;——通过MDIO接口配置与检测PHY芯片 - 没落骑士 - 博客园 https://www.cnblogs.com/moluoqishi/p/9118283.html一、前言   本文设计思想采用…...

FPGA 20个例程篇:13.千兆网口实现ARP通信协议(上)

第五章 外设接口通信&#xff0c;举一反三 13.千兆网口实现ARP通信协议 在以太网中&#xff0c;一个主机和另一个主机进行通信前&#xff0c;首先就需要知道其目的主机的MAC地址才可以进行正常通信&#xff0c;而目的MAC地址的获取正是由ARP协议所实现的。 其实关于以太网的知…...

基于FPGA的千兆以太网的实现(1)

基于FPGA的以太网图片接收项目简述UDP协议讲解V3学院的上位机传送图像数据的数据流项目的实验框图跨时钟域处理时序图Image_ctrl时序图工程代码测试模块的代码测试结果总结项目简述 本次实验我们将完成千兆以太网接收模块的设计。上位机利用千兆以太网发送图片到FPGA开发板&am…...

PHP“垂死挣扎”的十年!

点击“开发者技术前线”&#xff0c;选择“星标????”让一部分开发者看到未来作者 &#xff5c; Italo Baeza Cabrera 译者 &#xff5c; 张健欣 &#xff1b;来自&#xff1a;infoQ对于一门古老的语言来说&#xff0c;支撑未来技术的东西不是与时俱进吗&#xff1f;差不多…...

坚持#第380天~WMS仓库管理移动应用解决方案-二维码库存系统

沈阳工作感言 发生疫情了&#xff0c;我和经理都去不了沈阳&#xff0c;于是沈阳仓库黄了&#xff0c;法雷奥自己做了。 哈哈哈哈&#xff0c;仓库没有我和经理就不行呀&#xff0c;毕竟重点工作都是由我来做的。 好好总结一下我自己开发的系统吧&#xff08;幸好之前我早已料到…...

常用参考资料

微信小程序生成二维码&#xff0c;程序码&#xff1a; 微信小程序生成二维码、程序码、海报https://blog.csdn.net/Linlietao0587/article/details/124157581 地理信息相关&#xff1a; ArcGIS Enterprise10.8.1基础部署Linux版安装教程_最后的精灵的博客-CSDN博客_arcgis lin…...

解决微信小程序无法访问后台服务器问题

小程序可以调用我们后台的接口前提就是我们要配置一个合法域名。且开头为https形式。 扫码登陆微信公众平台->开发->开发管理->开发设置 如果没有域名要么就买一个&#xff0c;或者通过内网穿透&#xff0c;获取一个https域名。内网穿透工具有很多&#xff0c;我这里…...

微信小程序配置服务器域名

在开发微信小程序实现导出功能时用到了微信小程序的API--downloadFile&#xff0c;发现在开发工具上正常&#xff0c;但是在真机上不起作用&#xff0c;后来发现是这个api需要在后台配置服务器域名&#xff0c;下面是配置域名的步骤。 1、登录微信公众平台&#xff1a;https:/…...

如何本地调试微信小程序接口服务器

微信小程序所访问的接口路径需是合法域名且必须为 Https 协议&#xff0c;如果你作为微信小程序的接口服务器开发者&#xff0c;并且很不幸的接到了一个服务端异常(500)的反馈&#xff0c;你会如何调试&#xff1f; 一、束手束脚的服务端调试 若是浏览器端开发&#xff0c;还可…...

微信小程序如何设置服务器配置

最近微信小程序在it界火了起来,公司也要求我们开始接触微信小程序,废话不多说直接从配置微信小程序开始 1,首先,登录 https://mp.weixin.qq.com,(这里默认你已经获取到微信小程序的企业认证,而不是个人认证,也就是说你已经获取上线小程序的权利), 2,到"设置"界面,开发…...