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

CSP-J 2023 复赛第4题:旅游巴士

【题目来源】
https://www.luogu.com.cn/problem/P9751
https://www.acwing.com/problem/content/description/5313/

【题目描述】
小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。
旅游景点的地图共有 n 处地点,在这些地点之间连有 m 条道路。
其中
1 号地点为景区入口n 号地点为景区出口
我们把一天当中景区开门营业的时间记为 0 时刻,则从 0 时刻起,每间隔 k 单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。
所有道路均只能单向通行。
对于每条道路,游客步行通过的用时均为恰好 1 单位时间。
小 Z 希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是 k 的非负整数倍。
由于节假日客流众多,小 Z 在坐旅游巴士离开景区前只想一直沿着景区道路移动,而不想在任何地点(包括景区入口和出口)或者道路上停留。
出发前,小 Z 忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个“开放时间” ai,游客只有不早于 ai 时刻才能通过这条道路。
请帮助小 Z 设计一个旅游方案,使得他乘坐旅游巴士
离开景区的时间尽量地早

【输入格式】
输入的第一行包含 3 个正整数 n,m,k,表示旅游景点的地点数、道路数,以及旅游巴士的发车间隔。
输入的接下来 m 行,每行包含 3 个非负整数 ui,vi,ai,表示第 i 条道路从地点 ui 出发,到达地点 vi,道路的“开放时间”为 ai。

【输出格式】
输出一行,仅包含一个整数,表示小 Z 最早乘坐旅游巴士离开景区的时刻。
如果不存在符合要求的旅游方案,输出 -1。

【数据范围】
对于所有测试数据有:2≤n≤10^4,1≤m≤2×10^4,1≤k≤100,1≤ui,vi≤n,0≤ai≤10^6。

【输入样例】
5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1

【输出样例】
6

【样例解释】

小 Z 可以在 3 时刻到达景区入口,沿 1→3→4→5 的顺序走到景区出口,并在 6 时刻离开。

【算法分析】
本题需要用到的知识点:
○  priority_queue元素为结构体时需
重载 operator<
STL priority_queue 具有“自动排序”的强大功能。其默认使用 operator< 的比较方式进行排序。
但是,对于自定义类型(如结构体、联合体、枚举等),则必须重载 operator< 比较方式。
详见:
https://blog.csdn.net/hnjzsyjyj/article/details/124521165
例如,以下两段代码等价。

struct Node {int pr,index;
};
bool operator<(Node a,Node b) {return a.pr>b.pr;
}
struct Node {int pr,index;bool operator<(const Node &b) const {return pr>b.pr;}
};

○ 按结构体某一字段对结构体数组进行排序(C++) https://blog.csdn.net/hnjzsyjyj/article/details/120184972

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int inf=0x3f3f3f3f;
const int maxk=105;
const int maxn=10005;
vector<pair<int, int>> G[maxn];
int dis[maxn][maxk];
bool vis[maxn][maxk];
int n,m,k;struct Node {int x,y,d;bool operator<(const Node &W) const {return d>W.d;}
};void dijkstra() {priority_queue<Node> Q;memset(dis,inf,sizeof(dis));Q.push({1,0,dis[1][0]=0});while(Q.size()) {int x=Q.top().x;int y=Q.top().y;Q.pop();if(vis[x][y]) continue;vis[x][y]=1;for(int i=0; i<G[x].size(); i++) {int v=G[x][i].first;int w=G[x][i].second;int t=dis[x][y];int j=(y+1)%k;if(t<w) t+=(w-t+k-1)/k*k;if(dis[v][j]>t+1) Q.push({v,j,dis[v][j]=t+1});}}
}int main() {cin>>n>>m>>k; //scanf("%d%d%d",&n,&m,&k);while(m--) {int u,v,w;cin>>u>>v>>w; //scanf("%d%d%d",&u,&v,&w);G[u].push_back(make_pair(v,w));}dijkstra();if(dis[n][0]==inf) dis[n][0]=-1;cout<<dis[n][0]<<endl; //printf("%d\n",dis[n][0]);return 0;
}/*
in:
5 5 3
1 2 0
2 5 1
1 3 0
3 4 3
4 5 1out:
6
*/




【参考文献】
https://mp.weixin.qq.com/s/zckJsihxsDT2JNBFK1ipxA
https://www.acwing.com/problem/content/solution/5313/1/
https://www.luogu.com.cn/problem/solution/P9751
https://www.acwing.com/solution/content/214064/

相关文章:

CSP-J 2023 复赛第4题:旅游巴士

【题目来源】https://www.luogu.com.cn/problem/P9751https://www.acwing.com/problem/content/description/5313/【题目描述】 小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。 旅游景点的地图共有 n 处地点&#xff0c;在这些地点之间连有 m 条道路。 其中…...

JAVA算法和数据结构

一、Arrays类 1.1 Arrays基本使用 我们先认识一下Arrays是干什么用的&#xff0c;Arrays是操作数组的工具类&#xff0c;它可以很方便的对数组中的元素进行遍历、拷贝、排序等操作。 下面我们用代码来演示一下&#xff1a;遍历、拷贝、排序等操作。需要用到的方法如下 public…...

每日五道java面试题之spring篇(七)

目录&#xff1a; 第一题. 什么是Spring beans&#xff1f;第二题. 一个 Spring Bean 定义 包含什么&#xff1f;第三题. 如何给Spring 容器提供配置元数据&#xff1f;Spring有几种配置方式?第四题. Spring基于xml注入bean的几种方式?第五题&#xff1a;你怎样定义类的作用域…...

Keil编译GD32工程时找不到lib库文件

D:\Keil5\ARM\ARMCLANG\Bin\..\lib\armlib\mc_p.l:SELECTION_SCRIPT(2974): error: L6907E: Expected an expression. 问题 解决方法&#xff1a;因为编译器没有找到那个函数的代码&#xff0c;也就未解析了 其实问题很简单&#xff0c;把你的lib文件加进去&#xff0c;ok了…...

测试C#使用ViewFaceCore实现图片中的人脸遮挡

基于ViewFaceCore和DlibDotNet都能实现人脸识别&#xff0c;准备做个遮挡图片中人脸的程序&#xff0c;由于暂时不清楚DlibDotNet返回的人脸尺寸与像素的转换关系&#xff0c;最终决定使用ViewFaceCore实现图片中的人脸遮挡。   新建Winform项目&#xff0c;在Nuget包管理器中…...

2.21 Qt day2 菜单栏/工具栏/状态栏/浮动窗口、UI界面、信号与槽

思维导图 使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0c;…...

300分钟吃透分布式缓存-16讲:常用的缓存组件Redis是如何运行的?

Redis 基本原理 Redis 简介 Redis 是一款基于 ANSI C 语言编写的&#xff0c;BSD 许可的&#xff0c;日志型 key-value 存储组件&#xff0c;它的所有数据结构都存在内存中&#xff0c;可以用作缓存、数据库和消息中间件。 Redis 是 Remote dictionary server 即远程字典服务…...

上一篇文章补充:已经存在的小文件合并

对于HDFS上已经存在的大量小文件问题&#xff0c;有多种策略可以进行处理和优化&#xff1a; 1. **合并小文件**&#xff1a; - **使用Spark作业合并**&#xff1a;通过编写Spark程序读取小文件并调用repartition()或coalesce()函数重新分区数据&#xff0c;然后将合并后的…...

代码随想录训练营第三十期|第四十三天|动态规划 part05|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

1049. 最后一块石头的重量 II - 力扣&#xff08;LeetCode&#xff09; class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int n : stones) {sum n;}int target sum / 2;int[] dp new int[target 1];for (int i 0; i < stones.length; i…...

c++学习记录 string容器—字符串插入和删除

函数原型&#xff1a; string& insert(int pos,const char* s); //插入字符串string& insert(int pos,const string& str); //插入字符串string& insert(int pos,int n,char c); //在指定位置插入n个字符cstring&…...

【IEEE会议征稿】2024年第九届智能计算与信号处理国际学术会议(ICSP 2024)

2024年第九届智能计算与信号处理国际学术会议&#xff08;ICSP 2024&#xff09; 2024年第八届智能计算与信号处理国际学术会议&#xff08;ICSP 2024&#xff09;将在西安举行&#xff0c; 会期是2024年4月19-21日&#xff0c; 为期三天, 会议由西安科技大学主办。 欢迎参会&…...

【电机仿真】HFI算法脉振高频电压信号注入观测器-PMSM无感FOC控制

【电机仿真】HFI算法脉振高频电压信号注入观测器-PMSM无感FOC控制 文章目录 前言一、脉振高频电压注入法简介&#xff08;注入在旋转坐标系的d轴&#xff09;1.旋转高频电压&#xff08;电流&#xff09;注入法2.脉振高频电压注入法 二、高频注入理论1.永磁同步电机的高频模型2…...

Java学习——集合框架

Java集合框架&#xff08;Java Collections Framework&#xff09;是一套性能优良、使用方便的接口和类的集合&#xff0c;它位于java.util包下。这个框架包含了一系列集合接口的标准实现&#xff0c;比如列表、集合、队列&#xff0c;以及映射。使用这些集合&#xff0c;你可以…...

【鸿蒙 HarmonyOS 4.0】UIAbility、页面及组件的生命周期

一、背景 主要梳理下鸿蒙系统开发中常用的生命周期 二、UIAbility组件 UIAbility组件是一种包含UI界面的应用组件&#xff0c;主要用于和用户交互。 UIAbility组件是系统调度的基本单元&#xff0c;为应用提供绘制界面的窗口&#xff1b;一个UIAbility组件中可以通过多个页…...

jdk动态代理与CGLib动态代理

jdk动态代理 目标对象 package com.study;/*** 目标对象&#xff08;被代理的对象&#xff09;**/ public class Target implements TargetInf{public String name;public Target() {}public Target(String name) {this.name name;}public String buyCola (String name){Sys…...

Linux 命令行的世界 :4.操作文件和目录

此时此刻&#xff0c;我们已经准备好了做些真正的工作&#xff01;这一章节将会介绍以下命令&#xff1a; • cp —复制文件和目录 • mv —移动/重命名文件和目录 • mkdir —创建目录 • rm —删除文件和目录 • ln —创建硬链接和符号链接 图形文件管理器能轻松地实现…...

如何使用ArcGIS Pro生成等高线

无论在制图还是规划中&#xff0c;经常会使用到等高线&#xff0c;大多数情况下&#xff0c;从网上获取的高程数据都是DEM文件&#xff0c;我们可以通过ArcGIS Pro来生成等高线&#xff0c;这里为大家介绍一下生成方法&#xff0c;希望能对你有所帮助。 数据来源 教程所使用的…...

golang学习2,golang开发配置国内镜像

go env -w GO111MODULEon go env -w GOPROXYhttps://goproxy.cn,direct...

Stable Diffusion 绘画入门教程(webui)-ControlNet(线稿约束)

上篇文章介绍了openpose&#xff0c;本篇文章介绍下线稿约束&#xff0c;关于线稿约束有好几个处理器都属于此类型&#xff0c;但是有一些区别。 包含&#xff1a; 1、Canny(硬边缘&#xff09;&#xff1a;识别线条比较多比较细&#xff0c;一般用于更大程度得还原照片 2、ML…...

前端笔记——var let const 之间的区别

Var&#xff1a; 关键字来声明变量。它有以下特点&#xff1a; var声明的变量作用域是函数级的&#xff0c;即在函数内部声明的变量在整个函数范围内可见。 var变量可以被重复声明&#xff0c;而不会引发错误。 var变量会存在变量提升&#xff08;hoisting&#xff09;现象&…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...