塔子哥的环游之旅-腾讯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. 换座位 👨🏫 参考题解 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 替换生效 参考文献: 1 问题由来 我在算能SE5盒子上开发的时候,明显感觉很慢,然后看了下cpu内存竟然只有2.6G 但是这个盒子出厂默认是12G的,于…...
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筛选按钮为自定义按钮 前些时间做项目的时候,有个需求是,嫌elementui 自定的筛选按钮 下拉的小三角不好看,需要自定义按钮。 具体的实现方法如下: 从阿里的图片库引入自己想要的图标。在需要修改按钮的vue页…...
面向对象编程:一切皆对象
面向对象(OOP)是一种编程范式,它使用对象来设计软件。对象可以包含数据和代码:数据代表对象的状态,而代码代表操作数据的方式。在面向对象编程中,一切皆对象,这意味着将现实世界事务使用类与实例来模拟,如灯࿰…...
GIT版本管理与分支控制
目录 1、了解Git功能 2、第一次使用Git(首次配置好,后续不用再操作) 打开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.新时代是便捷的,要会用
各位读者朋友们: 我们现在AI时代的十字路口,AI是为生活带来便利的,我们要会使用AI。今天这篇文章来讲述一下AI的正确使用。 一、 AI的使用 1.1.便捷之中要会辨别 AI是带来强大的,利用好可以给生活带来便捷。 像之前WWDC24宣传…...
自定义线程池实现(一)
预期目标 1.实现一个相对完备的线程池 2.自定义拒绝策略(下一节) 线程池的基本参数 1.核心线程数 2.超时时间 3.拒绝策略(在下一篇中添加) 4.工作队列 5.任务队列 工作机制 当添加一个任务到线程池中时,线程池会…...
计算机毕业设计选题推荐-零食批发商仓库管理系统-Java/Python项目实战
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
基于springboot+vue+uniapp的校园快递平台小程序
开发语言:Java框架:springbootuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包&#…...
这两个大龄程序员,打算搞垮一个世界软件巨头!
大家都知道,Adobe是多媒体和数字内容创作者的绝对王者,它的旗下有众多大家耳熟能详的软件:Photoshop、Illustrator、Premiere Pro、After Effects、InDegign、Acrobat、Animate等等。 这些软件使用门槛很高,价格昂贵,安…...
LabVIEW放大器自动测量系统
开发了一个基于LabVIEW平台的多路前置放大器自动测量系统的开发与实施。该系统集成了硬件控制与软件编程,能够实现放大器各项性能指标的快速自动测量,有效提高了测试的精确性和效率。系统设计采用了虚拟仪器技术,结合了先进的测量与控制策略&…...
全面整理人工智能(AI)学习路线图及资源推荐
在人工智能(AI)飞速发展的今天,掌握AI技术已经成为了许多高校研究者和职场人士的必备技能。从深度学习到强化学习,从大模型训练到实际应用,AI技术的广度和深度不断拓展。作为一名AI学习者,面对浩瀚的知识海…...
react antd upload custom request处理多个文件上传
react antd upload custom request处理多个文件上传的问题 背景:第一次请求需要请求后端返回aws 一个link,再往link push文件,再调用另一个接口告诉后端已经上传成功,拿到返回值。 再把返回值传给业务api... 多文件上传一直是循环…...
ALB快速实现IPv4服务的负载均衡
阿里云应用型负载均衡ALB支持HTTP、HTTPS和QUIC协议,专门面向网络应用层,提供强大的业务处理能力。 为了实现IPv4服务的负载均衡,需要快速创建一个ALB实例,并将来自客户端的访问请求转发至后端服务器。 操作流程 第一步&#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_…...
优化网络接收缓存减少数据丢包
视频领域,网络udp数据丢包会引起视频解码花屏。 1、修订单个socket的缓冲区大小:通过setsockopt使用SO_RCVBUF来设置接收缓冲区,该参数在设置的时候不会与rmem_max进行对比校验,但是如果设置的大小超过rmem_max的话,则…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
