当前位置: 首页 > 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;则…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

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

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

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...