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

机试题——到邻国目标城市的最短距离

题目描述

A国与B国是相邻的两个国家,每个国家都有很多城市。国家内部有很多连接城市的公路,国家之间也有很多跨国公路,连接两个国家的边界城市。两个国家一共有N个城市,编号从1到N,一共有M条公路,包括国内公路与跨国公路。小明生活在A国的城市1(即编号为1的城市),想去B国的城市N游玩,由于小明办理的是只能入境一次的签证,所以从城市1到城市N的路径中,只能通过一条跨国公路。每条公路都有一个距离,并且通过这条公路会有一个花费。请帮小明计算出从城市1到城市N的最短距离,在距离最短的前提下,再计算出最少花费。如果无法到达城市N,输出-1。

输入描述

  • 第一行是一个整数N,表示两个国家的城市数量
  • 第二行是一个整数M,表示两个国家的公路数量,包括国内公路与跨国公路
  • 第三行是一个长度为N的字符串,字符串第i个(从1开始计数)字符为A或B,表示城市i属于A国或B国,其中第1个字符一定为A,第N个字符一定为B
  • 接下来M行,每行包含4个整数U, V, W, C,表示编号为U的城市与编号为V的城市之间存在一条公路,长度是W,花费是C。每条公路是双向的。

输出描述

  • 输出城市1到城市N的最短距离,并在距离最短的前提下,再输出最少花费。如果无法到达城市N,输出-1。

用例输入

5 5 
AABBB 
3 1 200 1 
2 3 150 3 
5 2 160 5 
4 3 170 7 
4 5 170 9
540 17

可以找到一条最优线路:城市1(A国) → 城市3(B国) → 城市4(B国) → 城市5(B国)。而且只通过一条跨国公路:城市1 → 城市3。

  • 距离 = 200 + 170 + 170 = 540
  • 花费 = 1 + 7 + 9 = 17

解题思路

我们可以使用 BFS (广度优先搜索)来解决这个问题。BFS 是处理最短路径问题的有效方法,但因为该问题同时涉及到 最短距离最小花费,并且约束条件是最多只能使用一次跨国公路,因此我们需要对状态进行细致管理。

我们定义一个 状态结构体 (State) 来表示每个城市的状态,包括当前城市编号、当前总距离、当前总花费以及是否已经过跨国公路。为了保证同时考虑距离和花费,我们将每个城市分为两种状态:

  • flag = 0 表示还没有经过跨国公路。
  • flag = 1 表示已经经过一次跨国公路。

使用 队列 (queue) 来模拟 BFS,对于每条公路(国内或跨国),根据是否是跨国公路的条件进行更新:

  • 对于 国内公路,可以继续前进。
  • 对于 跨国公路,只能走一次,且必须确保不重复跨国。

最终,通过 BFS 搜索完成后,输出到达城市N的最短距离和最小花费。

优化点:使用优先队列

代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;struct Edge {int u, v, w, c;
};struct State {int dist, cost, node, flag;bool operator>(const State& other) const {// 优先按距离排,再按花费排if (dist == other.dist) {return cost > other.cost;}return dist > other.dist;}
};int main() {int n, m;cin >> n >> m;string countries;cin >> countries;vector<vector<Edge>> graph(n + 1);  // 图的邻接表// 读取公路信息for (int i = 0; i < m; i++) {int u, v, w, c;cin >> u >> v >> w >> c;graph[u].push_back({ u, v, w, c });graph[v].push_back({ v, u, w, c });}// 初始化距离和花费vector<int> dist(n + 1, INT_MAX);vector<int> cost(n + 1, INT_MAX);dist[1] = 0;cost[1] = 0;priority_queue<State, vector<State>, greater<State>> pq;pq.push({ 0, 0, 1, 0 });  // 从城市1开始,距离0,花费0,未跨国while (!pq.empty()) {State current = pq.top();pq.pop();int u = current.node;int current_dist = current.dist;int current_cost = current.cost;int current_flag = current.flag;if (current_dist > dist[u] || (current_dist == dist[u] && current_cost > cost[u])) {continue;  // 如果当前状态不是最优的,跳过}for (const Edge& edge : graph[u]) {int v = edge.v;int next_dist = current_dist + edge.w;int next_cost = current_cost + edge.c;bool isSameCountry = (countries[u - 1] == countries[v - 1]);if (isSameCountry) {// 国内公路,继续走if (next_dist < dist[v] || (next_dist == dist[v] && next_cost < cost[v])) {dist[v] = next_dist;cost[v] = next_cost;pq.push({ next_dist, next_cost, v, current_flag });}}else {// 跨国公路,只能走一次if (current_flag == 0) {if (next_dist < dist[v] || (next_dist == dist[v] && next_cost < cost[v])) {dist[v] = next_dist;cost[v] = next_cost;pq.push({ next_dist, next_cost, v, 1 });}}}}}// 输出结果if (dist[n] == INT_MAX) {cout << -1 << endl;  // 如果无法到达城市N}else {cout << dist[n] << " " << cost[n] << endl;  // 输出最短距离和最小花费}return 0;
}

相关文章:

机试题——到邻国目标城市的最短距离

题目描述 A国与B国是相邻的两个国家&#xff0c;每个国家都有很多城市。国家内部有很多连接城市的公路&#xff0c;国家之间也有很多跨国公路&#xff0c;连接两个国家的边界城市。两个国家一共有N个城市&#xff0c;编号从1到N&#xff0c;一共有M条公路&#xff0c;包括国内…...

Python + Tkinter + pyttsx3实现的桌面版英语学习工具

Python Tkinter pyttsx3实现的桌面版英语学习工具 在多行文本框输入英文句子&#xff0c;双击其中的英文单词&#xff0c;给出英文读音和中文含义和音标。 本程序查询本地词典数据。通过菜单栏"文件"->"打开词典编辑器"进入编辑界面。 词典数据存储…...

【Vite + Vue + Ts 项目三个 tsconfig 文件】

Vite Vue Ts 项目三个 tsconfig 文件 为什么 Vite Vue Ts 项目会有三个 tsconfig 文件&#xff1f;首先我们先了解什么是 tsconfig.json ? 为什么 Vite Vue Ts 项目会有三个 tsconfig 文件&#xff1f; 在使用 Vite 创建 vue-ts 模板的项目时&#xff0c;会发现除了 ts…...

AI时代IT行业职业方向规划大纲

一、引言 AI时代的颠覆性影响 ChatGPT、Midjourney等生成式AI对传统工作模式的冲击 案例&#xff1a;AI编程助手&#xff08;GitHub Copilot&#xff09;改变开发者工作流程 核心问题&#xff1a;IT从业者如何避免被AI替代&#xff0c;并找到新机遇&#xff1f; 二、AI时代…...

Mac M1 Comfyui 使用MMAudio遇到的问题解决?

问题1: AssertionError: Torch not compiled with CUDA enabled&#xff1f; 解决办法&#xff1a;修改代码以 CPU 运行 第一步&#xff1a;找到 /ComfyUI/custom_nodes/ComfyUI-MMAudio/mmaudio/ext/autoencoder/vae.py文件中的下面这两行代码 self.data_mean nn.Buffer(t…...

大语言模型深度研究功能:人类认知与创新的新范式

在人工智能迅猛发展的今天&#xff0c;大语言模型&#xff08;LLM&#xff09;的深度研究功能正在成为重塑人类认知方式的关键力量。这一突破性技术不仅带来了工具层面的革新&#xff0c;更深刻地触及了人类认知能力的本质。本文将从认知科学的角度出发&#xff0c;探讨LLM如何…...

[SAP ABAP] 性能优化

1.数据库编程OPEN SQL方面优化 1.避免使用SELECT *&#xff0c;只查询需要的字段即可 尽量使用SELECT f1 f2 ... (具体字段) 来代替 SELECT * 写法 2. 如果确定只查询一条数据时&#xff0c;使用 SELECT SINGLE... 或者是 SELECT ...UP TO 1 ROWS ... 使用语法 UP TO n ROWS 来…...

并行计算、分布式计算与云计算:概念剖析与对比研究(表格对比)

什么是并行计算&#xff1f;什么是分布计算&#xff1f;什么是云计算&#xff1f;我们如何更好理解这3个概念&#xff0c;我们采用概念之间的区别和联系的方式来理解&#xff0c;做到切实理解&#xff0c;深刻体会。 1、并行计算与分布式计算 并行计算、分布式计算都属于高性…...

ASP.NET Core Filter

目录 什么是Filter&#xff1f; Exception Filter 实现 注意 ActionFilter 注意 案例&#xff1a;自动启用事务的筛选器 事务的使用 TransactionScopeFilter的使用 什么是Filter&#xff1f; 切面编程机制&#xff0c;在ASP.NET Core特定的位置执行我们自定义的代码。…...

doris:删除操作概述

在 Apache Doris 中&#xff0c;删除操作&#xff08;Delete&#xff09;是一项关键功能&#xff0c;用于管理和清理数据&#xff0c;以满足用户在大规模数据分析场景中的灵活性需求。 Doris 提供了丰富多样的删除功能支持&#xff0c;包括&#xff1a;DELETE 语句、删除标记&…...

【思维导图】redis

学习计划&#xff1a;将目前已经学的知识点串成一个思维导图。在往后的学习过程中&#xff0c;不断往思维导图里补充&#xff0c;形成自己整个知识体系。对于思维导图里的每个技术知识&#xff0c;自己用简洁的话概括出来&#xff0c; 训练自己的表达能力。...

申博经验贴

1. 所谓申博&#xff0c;最重要的就是定制的海投 分成两个部分 1. 定制 要根据每个教授去写不同的&#xff0c;一定不要泛泛的去写&#xff0c;一定要非常非常的具体&#xff0c;要引起教授的兴趣。每个教授每天都会收到几十封邮件&#xff0c;所以要足够的引起教授的注意&a…...

.Net Core笔记知识点(跨域、缓存)

设置前端跨域配置示例&#xff1a; builder.Services.AddCors(option > {option.AddDefaultPolicy(policy > {policy.WithOrigins(originUrls).AllowAnyMethod().AllowAnyHeader().AllowCredentials();});});var app builder.Build();app.UseCors(); 【客户端缓存】接…...

YOLOV11-1:YoloV11-安装和CLI方式训练模型

YoloV11-安装和CLI方式训练模型 1.安装和运行1.1安装的基础环境1.2安装yolo相关组件1.3命令行方式使用1.3.1 训练1.3.2 预测 本文介绍yoloV11的安装和命令行接口 1.安装和运行 1.1安装的基础环境 GPU环境&#xff0c;其中CUDA是12.4版本 1.2安装yolo相关组件 # 克隆github…...

自学习记录-编程语言的特点(持续记录)

我学习的顺序是C -> python -> C -> Java。在讲到某项语言的特点是&#xff0c;可能会时不时穿插其他语言的特点。 Java 1 注解Annotation Python中也有类似的Decorators。以下为AI学习了解到的&#xff1a; Java的Annotation是一种元数据&#xff08;metadata)&a…...

TypeScript (TS) 和 JavaScript (JS)

TypeScript (TS) 和 JavaScript (JS) 的区别主要在于 TypeScript 是 JavaScript 的一个超集&#xff0c;它在 JavaScript 基础上增加了类型系统和一些高级功能。让我们详细看看两者的区别和关系&#xff1a; 类型系统&#xff1a; TypeScript 最大的特点是 静态类型。在 TypeSc…...

【HarmonyOS之旅】基于ArkTS开发(二) -> UI开发三

目录 1 -> 绘制图形 1.1 -> 绘制基本几何图形 1.2 -> 绘制自定义几何图形 2 -> 添加动画效果 2.1 -> animateTo实现闪屏动画 2.2 -> 页面转场动画 3 -> 常见组件说明 1 -> 绘制图形 绘制能力主要是通过框架提供的绘制组件来支撑&#xff0c;支…...

如何选择Spring AOP的动态代理?JDK与CGLIB的适用场景?

在Spring AOP中&#xff0c;选择JDK动态代理还是CGLIB动态代理取决于目标对象的特性以及具体需求。以下是两种代理方式的适用场景和特点&#xff1a; JDK动态代理 • 适用场景&#xff1a; • 目标对象实现了接口&#xff1a;JDK动态代理要求目标对象必须实现至少一个接口&a…...

手机连接WIFI可以上网,笔记本电脑连接WIFI却不能上网? 解决方法?

原因&#xff1a;DNS受污染了 解决办法 step 1&#xff1a;清空域名解析记录&#xff08;清空DNS&#xff09; ipconfig /flushdns (Windows cmd命令行输入) step 2&#xff1a;重新从DHCP 获取IP ipconfig /release&#xff08;释放当前IP地址&#xff09; ipconfig /renew &…...

MySQL不适合创建索引的11种情况

文章目录 前言1. **数据量小的表**2. **频繁更新的列**3. **低选择性的列**4. **频繁插入和删除的表**5. **查询中很少使用的列**6. **大文本或BLOB列**7. **复合索引中未使用的前导列**8. **频繁进行批量插入的表**9. **查询返回大部分数据的表**10. **临时表**11. **列值频繁…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)

前言&#xff1a; 在Java编程中&#xff0c;类的生命周期是指类从被加载到内存中开始&#xff0c;到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期&#xff0c;让读者对此有深刻印象。 目录 ​…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...