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

UVa11374 Airport Express(Dijkstra)

题意

给出经济路线以及商业路线,在给出起始点s,终止点e,在只能使用其中一个商业路线 的情况下输出最短路径

思路

如果选择商业路线为从u到v,则需要从s->u,u->v,v->e点的路径最短。使用Dijkstra计算出从s点到其它各点,以及从e点到其它各点的最短路径,然后遍历商业路线u,v,选取从s->u,u->v,v->e点中路线最短的

代码

#include <bits/stdc++.h>using namespace std;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)struct Edge
{int u, v, d;
};struct HeapNode
{int u, d;bool operator<(const HeapNode& other) const{return d > other.d;}
};template <int SZV, int INF>
struct Dijkstra
{int n;vector<Edge> edges;vector<int> graph[SZV];bool done[SZV];int d[SZV], p[SZV];void init(int n){this->n = n;edges.clear();_for(i, 0, n) {graph[i].clear();}}void addEdge(int u, int v, int d){graph[u].push_back(edges.size());edges.push_back({u, v, d});}void dijkstra(int s){priority_queue<HeapNode> pq;fill_n(done, n, false);fill_n(d, n, INF);d[s] = 0;pq.push({s, 0});while (!pq.empty()) {HeapNode curNode = pq.top();pq.pop();int u = curNode.u;if (done[u]) {continue;}done[u] = true;_for(i, 0, graph[u].size()) {const auto& edge = edges[graph[u][i]];int v = edge.v;if (d[u] + edge.d < d[v]) {d[v] = d[u] + edge.d;p[v] = graph[u][i];pq.push({v, d[v]});}}}}void getPath(int s, int e, deque<int>& path, bool rev = false){int x = e;if (rev) {path.push_back(x);} else {path.push_front(x);}while (x != s) {x = edges[p[x]].u;if (rev) {path.push_back(x);} else {path.push_front(x);}}}
};void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}const int MAXN = 500 + 4;
const int INF = 1e9;int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint N, S, E;int kase = 0;while (cin >> N >> S >> E) {if (kase++) {cout << endl;}Dijkstra<MAXN, INF> sd, ed;sd.init(N + 1); ed.init(N + 1);int M;cin >> M;_for(i, 0, M) {int X, Y, Z;cin >> X >> Y >> Z;sd.addEdge(X, Y, Z);sd.addEdge(Y, X, Z);ed.addEdge(X, Y, Z);ed.addEdge(Y, X, Z);}sd.dijkstra(S);ed.dijkstra(E);int cu = -1;int ans = INF;deque<int> path;if (sd.d[E] < ans) {ans = sd.d[E];sd.getPath(S, E, path);}auto update = [&](int u, int v, int d) {if (sd.d[u] < ans && ed.d[v] < ans && sd.d[u] + d + ed.d[v] < ans) {ans = sd.d[u] + d + ed.d[v];cu = u;path.clear();sd.getPath(S, u, path);ed.getPath(E, v, path, true);}};int K;cin >> K;_for(i, 0, K) {int u, v, d;cin >> u >> v >> d;update(u, v, d);update(v, u, d);}_for(i, 0, path.size()) {if (i) {cout << " ";}cout << path[i];}cout << endl;if (cu == -1) {cout << "Ticket Not Used" << endl;} else {cout << cu << endl;}cout << ans << endl;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}

相关文章:

UVa11374 Airport Express(Dijkstra)

题意 给出经济路线以及商业路线&#xff0c;在给出起始点s&#xff0c;终止点e&#xff0c;在只能使用其中一个商业路线 的情况下输出最短路径 思路 如果选择商业路线为从u到v&#xff0c;则需要从s->u,u->v&#xff0c;v->e点的路径最短。使用Dijkstra计算出从s点…...

hadoop的hdfs中避免因节点掉线产生网络风暴

hadoop的hdfs中避免因节点掉线产生网络风暴 控制节点掉线RPC风暴的参数 三个参数都是hdfs-site.xml中参数&#xff0c;具体可以参考apache hadoop官网&#xff0c;其实块的复制速度有两个方面决定&#xff0c;一是namenode分发任务的速度&#xff0c;二则是datanode之间进行复…...

2023年高教社杯 国赛数学建模思路 - 案例:最短时间生产计划安排

文章目录 0 赛题思路1 模型描述2 实例2.1 问题描述2.2 数学模型2.2.1 模型流程2.2.2 符号约定2.2.3 求解模型 2.3 相关代码2.4 模型求解结果 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 最短时…...

Spring MVC介绍

MVC模式是什么 MVC 模式&#xff0c;全称为 Model-View-Controller&#xff08;模型-视图-控制器&#xff09;模式&#xff0c;它是一种软件架构模式&#xff0c;其目标是将软件的用户界面&#xff08;即前台页面&#xff09;和业务逻辑分离&#xff0c;使代码具有更高的可扩展…...

5年测试在职经验之谈:2年功能测试、3年自动化测试,从入门到不可自拔...

毕业3年了&#xff0c;学的是环境工程专业&#xff0c;毕业后零基础转行做软件测试。 已近从事测试行业8年了&#xff0c;自己也从事过2年的手工测试&#xff0c;从事期间越来越觉得如果一直在手工测试的道路上前进&#xff0c;并不会有很大的发展&#xff0c;所以通过自己的努…...

【Python数据分析】数据分析之numpy基础

实验环境&#xff1a;建立在Python3的基础之上 numpy提供了一种数据类型&#xff0c;提供了数据分析的运算基础&#xff0c;安装方式 pip install numpy导入numpy到python项目 import numpy as np本文以案例的方式展示numpy的基本语法&#xff0c;没有介绍语法的细枝末节&am…...

Swift 如何从图片数据(Data)检测原图片类型?

功能需求 如果我们之前把图片对应的数据(Data)保持在内存或数据库中,那么怎么从 Data 对象检测出原来图片的类型呢? 如上图所示:我们将 11 张不同类型的图片转换为 Data 数据,然后从 Data 对象正确检测出了原图片类型。 目前,我们的代码可以检测出 jpeg(jpg), tiff,…...

【ES6】 JavaScript 中的Object.assign

Object.assign() 是 JavaScript 中的一个方法&#xff0c;它用于复制源对象的所有可枚举属性到目标对象。该方法会返回目标对象。 这是其基本用法&#xff1a; let target Object.assign({}, source);在这个例子中&#xff0c;source 对象的所有可枚举属性都被复制到了 targ…...

Redis缓存和持久化

目录 Redis缓存 什么是缓存 缓存更新策略​编辑 业务场景 缓存穿透 常见的解决方案 缓存雪崩 解决方案 缓存击穿 解决方案 Redis持久化 RDB持久化 执行时机 RDB方式bgsave的基本流程 AOF持久化 RDB和AOF的对比​编辑 Redis主从 数据同步原理 总结 Redis缓存 …...

OpenCV(六):多通道分离与合并

目录 1.多通道分离split() 2.多通道合并merge() 3.Android JNI demo 1.多通道分离split() void cv::split ( InputArray m, OutputArrayOfArrays mv &#xff09; m:待分离的多通道图像。 mv:分离后的单通道图像&#xff0c;为向量vector形式。 2.多通道合并merge…...

Sql单行数据查询为多行

数据量小可以&#xff0c;数据量大时间太久 select distinct regexp_substr("fixed_option", [^,],1,level) c1 from "MATERIAL"."BasicInfo_Dishes_Summary" A where "fixed_option" is not NULL AND "dish_name"地三鲜…...

网络协议分析-http/https/tcp/udp

文章目录 TCP三次握手/TCP三次挥手TCP三次握手TCP四次挥手完整报文 实例代码HttpSampleClientHttpSampleServerHttpsSampleClientHttpsSampleServerTcpSampleClientTcpSampleServerUdpSampleClientUdpSampleSever 资料 TCP三次握手/TCP三次挥手 “三次握手”的目的是“为了防止…...

基于aarch64分析kernel源码 四:printk 内核打印

一、参考 Message logging with printk — The Linux Kernel documentation 如何获得正确的printk格式占位符 — The Linux Kernel documentation 使用printk记录消息 — The Linux Kernel documentation printk 内核打印 – 人人都懂物联网 (getiot.tech) 内核printk原理…...

机器人中的数值优化(六)—— 线搜索最速下降法

本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考&#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等&#xff0c;本系列文章篇数较多&#xff0c;不定期更新&#xff0c;上半部分介绍无约束优化&#xff0c;…...

postman调试注意事项

Postman是一个强大的API调试工具&#xff0c;它可以帮助开发人员测试和调试API端点&#xff0c;以确保它们按预期工作。在使用Postman进行接口调试时&#xff0c;以下是一些注意事项和可能出现的问题&#xff0c;以及如何解决这些问题。 确保请求参数正确 在测试API接口时&am…...

【C#】泛型

【C#】泛型 泛型是什么 泛型是将类型作为参数传递给类、结构、接口和方法&#xff0c;这些参数相当于类型占位符。当我们定义类或方法时使用占位符代替变量类型&#xff0c;真正使用时再具体指定数据类型&#xff0c;以此来达到代码重用目的。 泛型特点 提高代码重用性一定…...

CLIP:连接文本-图像

Contrastive Language-Image Pre-Training CLIP的主要目标是通过对比学习&#xff0c;学习匹配图像和文本。CLIP最主要的作用&#xff1a;可以将文本和图像表征映射到同一个表示空间 这是通过训练模型来预测哪个图像属于给定的文本&#xff0c;反之亦然。在训练过程中&#…...

MFC网络编程简单例程

目录 一、关于网络的部分概念1 URL(网址)及URL的解析2 URL的解析3 域名及域名解析3 IP及子网掩码4 什么是Web服务器5 HTTP的基本概念6 Socket库概念7 协议栈8 Socket库收发数据基本步骤 二、基于TCP的网络应用程序三、基于UDP的网络应用程序 一、关于网络的部分概念 1 URL(网址…...

云原生简介 (Cloud Native)

云原生&#xff08;cloud Native&#xff09; 云原生的概念诞生于10年前&#xff0c;netflix 在 AWS 上的一次演讲中。有趣的是当初没有明确的定义&#xff0c;现在也没有明确的定义&#xff0c;对不同的人来说&#xff0c;有不同的概念。 概念 云原生&#xff1a;是在云上构…...

【SpringBoot系列】 测试框架之@SpringBootTest的使用

SpringBootTest的详细介绍 SpringBootTest 是 Spring Boot 测试框架中的注解&#xff0c;用于标识一个测试类&#xff0c;以指示该类是一个 Spring Boot 应用程序的测试类。它允许你在测试环境中加载整个 Spring Boot 应用程序上下文&#xff0c;测试应用程序的各种组件、服务…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...

Tauri2学习笔记

教程地址&#xff1a;https://www.bilibili.com/video/BV1Ca411N7mF?spm_id_from333.788.player.switch&vd_source707ec8983cc32e6e065d5496a7f79ee6 官方指引&#xff1a;https://tauri.app/zh-cn/start/ 目前Tauri2的教程视频不多&#xff0c;我按照Tauri1的教程来学习&…...