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

塔子哥的环游之旅-腾讯2023笔试(codefun2000)

题目链接
塔子哥的环游之旅-腾讯2023笔试(codefun2000)

题目内容

塔子哥是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游。
在这个国家,每个城市都有一个固定的时间 ai ,表示在该城市中转换交通工具所需的时间。特别地,在出发城市 1 和目的地城市 n,塔子哥不需要转换交通工具。
塔子哥可以自由选择乘坐飞机或火车前往下一个城市。他希望能够以最短的时间从出发城市抵达目的地城市。保证任意两个城市之间是连通的。

输入描述

第一行三个整数,以空格分开,分别表示

输出描述

输出一个整数,表示塔子哥从出发城市到达目的地城市所需的最短时间。

样例1

输入

3 3
1 1 1
1 2 1 1
2 3 1 2
2 3 1 2

输出

3

样例1解释

塔子哥可以按照以下路线行进:从城市 1 乘坐飞机前往城市 2,耗时 1 个单位时间。在城市 2 中转换交通工具,耗时 1 个单位时间。从城市 2 乘坐火车前往城市 3,耗时 1 个单位时间。总共耗时 3 个单位时间,无法再缩短时间。

题解1

// 使用堆优化的迪杰斯特拉算法,时间复杂度是O((m+n)logn),其中n是图中顶点个数,m是图中边的条数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int N = 1e5 + 10;int n, m, a[N];
LL dis[N][2]; // dis[i][0/1]表示到达编号为i的城市的飞机场/火车站所需的最少时间 
bool vis[N][2]; // viss[i][0/1]表示途中是否经过编号为i的城市的飞机场/火车站,1:表示已经过,2:表示没有经过 
struct node{int to, t, w; /*to表示边的终点t表示线路类别:0:该线路为飞机线路 1:该线路为火车线路w表示行驶该路线所需的时间 */ 
};
vector<node> edge[N];struct Vnode{int startNode;int t;LL w;/*to表示边的起点t表示线路类别:0:该线路为飞机线路 1:该线路为火车线路w表示行驶该路线所需的时间 */ 
}now;bool cmp(Vnode A, Vnode B){if(A.w != B.w) return A.w > B.w;return A.startNode > B.startNode;
} 
//  decltype为c++11中的关键字,decltype(&cmp)获取了比较函数cmp的类型
priority_queue<Vnode, vector<Vnode>, decltype(&cmp)> pq(cmp); // 小顶堆 void dijstra(){for(int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = INF;dis[1][1]= dis[1][0] = 0;pq.push({1,0,0}); // 从1号城市的飞机站出发, pq.push({1,1,0}); // 从1号城市的火车站出发, while(!pq.empty()){now = pq.top();pq.pop();int u = now.startNode;int ut = now.t;if(!vis[u][ut]){vis[u][ut] = 1;int sz = int(edge[u].size());for(int j = 0; j < sz; j++){int v = edge[u][j].to;int w = edge[u][j].w;int vt = edge[u][j].t;if(!vis[v][vt]){/*1)如果到达当前的站的类别与出发站的类别相同,则不需要转换交通工具所需的时间2)如果到达当前的站的类别与出发站的类别不相同,则需要转换交通工具所需的时间*/ if(vt == ut) dis[v][vt] = min(dis[v][vt], dis[u][vt] + w);else dis[v][vt] = min(dis[v][vt], dis[u][ut]+a[u]+w);pq.push({v,vt, dis[v][vt]});}}}}
}
int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1, u, v, w, t; i <= m; i++){scanf("%d%d%d%d", &u, &v, &w, &t);t--;edge[u].push_back({v, t, w});edge[v].push_back({u, t, w});}dijstra();printf("%lld\n", min(dis[n][0], dis[n][1]));return 0;
}

相关文章:

塔子哥的环游之旅-腾讯2023笔试(codefun2000)

题目链接 塔子哥的环游之旅-腾讯2023笔试(codefun2000) 题目内容 塔子哥是一位热衷旅游的程序员。他所在的国家共有 n 个城市,编号从 1 到 n。这些城市之间有 m 条双向的交通线路,分别为飞机线路和火车线路。塔子哥起始位于编号为 1 的城市,他计划前往编号为 n 的城市进行旅游…...

力扣SQL50 换座位

Problem: 626. 换座位 &#x1f468;‍&#x1f3eb; 参考题解 Code SELECT(CASEWHEN MOD(id, 2) ! 0 AND counts ! id THEN id 1WHEN MOD(id, 2) ! 0 AND counts id THEN idELSE id - 1END) AS id,student FROMseat,(SELECTCOUNT(*) AS countsFROMseat) AS seat_counts O…...

SOPHGO算能科技BM1684芯片修改内存布局

目录 1 问题由来 2 下载memory_edit工具 3 查看当前内存配置 3 修改内存布局 4 替换生效 参考文献&#xff1a; 1 问题由来 我在算能SE5盒子上开发的时候&#xff0c;明显感觉很慢&#xff0c;然后看了下cpu内存竟然只有2.6G 但是这个盒子出厂默认是12G的&#xff0c;于…...

CUDA实现矩阵乘法的性能优化策略

本人主要参考了https://zhuanlan.zhihu.com/p/435908830,https://zhuanlan.zhihu.com/p/410278370,https://zhuanlan.zhihu.com/p/518857175 ,下面的代码均是本人实现 矩阵乘法的easy实现-V1 C = A B , A ∈ R M K , B ∈ R K...

element ui 修改table筛选按钮为自定义按钮

element ui 修改table筛选按钮为自定义按钮 前些时间做项目的时候&#xff0c;有个需求是&#xff0c;嫌elementui 自定的筛选按钮 下拉的小三角不好看&#xff0c;需要自定义按钮。 具体的实现方法如下&#xff1a; 从阿里的图片库引入自己想要的图标。在需要修改按钮的vue页…...

面向对象编程:一切皆对象

面向对象(OOP)是一种编程范式,它使用对象来设计软件。对象可以包含数据和代码&#xff1a;数据代表对象的状态&#xff0c;而代码代表操作数据的方式。在面向对象编程中&#xff0c;一切皆对象&#xff0c;这意味着将现实世界事务使用类与实例来模拟&#xff0c;如灯&#xff0…...

GIT版本管理与分支控制

目录 1、了解Git功能 2、第一次使用Git&#xff08;首次配置好&#xff0c;后续不用再操作&#xff09; 打开git后端 设置用户签名 结果 3、初始项目架构 创建本地新仓库并初始化 文件添加到本地仓库 a.文件添加缓存区 b.缓存区内容提交到本地仓库 c.改写提交的注释 …...

大模型算法备案流程最详细说明【流程+附件】

文章目录 一、语料安全评估 二、黑盒测试 三、模型安全措施评估 四、性能评估 五、性能评估 六、安全性评估 七、可解释性评估 八、法律和合规性评估 九、应急管理措施 十、材料准备 十一、【线下流程】大模型备案线下详细步骤说明 十二、【线上流程】算法备案填报…...

JAVA GUI 基本使用

package com.lu.gui;import javax.swing.*; import java.awt.*;public class MyJFrame extends JFrame {public MyJFrame() {this.setBackground(Color.BLACK);this.setResizable(false);this.setSize(500,500);this.setTitle("登录页面");} }package com.lu.gui;imp…...

【涵子来信】——AI革新:1.新时代是便捷的,要会用

各位读者朋友们&#xff1a; 我们现在AI时代的十字路口&#xff0c;AI是为生活带来便利的&#xff0c;我们要会使用AI。今天这篇文章来讲述一下AI的正确使用。 一、 AI的使用 1.1.便捷之中要会辨别 AI是带来强大的&#xff0c;利用好可以给生活带来便捷。 像之前WWDC24宣传…...

自定义线程池实现(一)

预期目标 1.实现一个相对完备的线程池 2.自定义拒绝策略&#xff08;下一节&#xff09; 线程池的基本参数 1.核心线程数 2.超时时间 3.拒绝策略&#xff08;在下一篇中添加&#xff09; 4.工作队列 5.任务队列 工作机制 当添加一个任务到线程池中时&#xff0c;线程池会…...

计算机毕业设计选题推荐-零食批发商仓库管理系统-Java/Python项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

基于springboot+vue+uniapp的校园快递平台小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…...

这两个大龄程序员,打算搞垮一个世界软件巨头!

大家都知道&#xff0c;Adobe是多媒体和数字内容创作者的绝对王者&#xff0c;它的旗下有众多大家耳熟能详的软件&#xff1a;Photoshop、Illustrator、Premiere Pro、After Effects、InDegign、Acrobat、Animate等等。 这些软件使用门槛很高&#xff0c;价格昂贵&#xff0c;安…...

LabVIEW放大器自动测量系统

开发了一个基于LabVIEW平台的多路前置放大器自动测量系统的开发与实施。该系统集成了硬件控制与软件编程&#xff0c;能够实现放大器各项性能指标的快速自动测量&#xff0c;有效提高了测试的精确性和效率。系统设计采用了虚拟仪器技术&#xff0c;结合了先进的测量与控制策略&…...

全面整理人工智能(AI)学习路线图及资源推荐

在人工智能&#xff08;AI&#xff09;飞速发展的今天&#xff0c;掌握AI技术已经成为了许多高校研究者和职场人士的必备技能。从深度学习到强化学习&#xff0c;从大模型训练到实际应用&#xff0c;AI技术的广度和深度不断拓展。作为一名AI学习者&#xff0c;面对浩瀚的知识海…...

react antd upload custom request处理多个文件上传

react antd upload custom request处理多个文件上传的问题 背景&#xff1a;第一次请求需要请求后端返回aws 一个link&#xff0c;再往link push文件&#xff0c;再调用另一个接口告诉后端已经上传成功&#xff0c;拿到返回值。 再把返回值传给业务api... 多文件上传一直是循环…...

ALB快速实现IPv4服务的负载均衡

阿里云应用型负载均衡ALB支持HTTP、HTTPS和QUIC协议&#xff0c;专门面向网络应用层&#xff0c;提供强大的业务处理能力。 为了实现IPv4服务的负载均衡&#xff0c;需要快速创建一个ALB实例&#xff0c;并将来自客户端的访问请求转发至后端服务器。 操作流程 第一步&#x…...

【LLM】-12-部署Langchain-Chatchat-0.3.x版本

目录 1、0.3与0.2的功能对比 2、0.3.x支持多种部署方式 2.3、源码安装 2.3.1、项目源码下载 2.3.2、创建conda环境 2.3.3、安装poetry 2.3.4、安装依赖库 2.3.5、项目初始化 2.3.6、配置文件 2.3.7、初始化知识库 2.3.7、启动服务 2.3.8、配置说明 2.3.8.1、basic_…...

优化网络接收缓存减少数据丢包

视频领域&#xff0c;网络udp数据丢包会引起视频解码花屏。 1、修订单个socket的缓冲区大小&#xff1a;通过setsockopt使用SO_RCVBUF来设置接收缓冲区&#xff0c;该参数在设置的时候不会与rmem_max进行对比校验&#xff0c;但是如果设置的大小超过rmem_max的话&#xff0c;则…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...