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

VOJ 迷阵突围 题解 次短路径 dijkstra算法

迷阵突围

题目描述

小明陷入了坐标系上的一个迷阵,迷阵上有 n 个点,编号从 1 到 n 。小明在编号为 1 的位置,他想到编号为 n 的位置上。小明当然想尽快到达目的地,但是他觉得最短的路径可能有风险,所以他会选择第二短的路径。现在小明知道了 n 个点的坐标,以及哪些点之间是相连的,他想知道第二短的路径长度是多少。

注意,每条路径上不能重复经过同一个点

输入描述

第一行输入两个整数 n ( 1 ≤ n ≤ 200 1 ≤ n ≤ 200 1n200 ) 和 m ,表示一共有 n 个点和 m 条边。
接下来输入 n 行,每行输入两个整数 x i x_i xi y i y_i yi( − 500 ≤ x i −500 ≤ x_i 500xi y i ≤ 500 y_i ≤ 500 yi500 ),代表第 i i i 个点的坐标。
接下来输入 m 行,每行输入两个整数 p j p_j pj q j q_j qj( 1 ≤ p j 1 ≤ p_j 1pj q j ≤ n q_j ≤ n qjn ),表示点 p j p_j pj 和点 q j q_j qj 之间相连。

输出描述

输出一行,输出包含一个数,表示第二短的路径长度(小数点后面保留两位),如果第一短路径有多条,则答案就是第一最短路径的长度;如果第二最短路径不存在,则输出 −1 。

样例 #1

样例输入 #1

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

样例输出 #1

2.41

思路

求次短路径长度分为两种:一种是可以重复经过一个点的,另一种是不能重复经过一个点的。前者解题策略是用dis1和dis2分别记录最短路长度和次短路长度,并在更新过程中依次判断是否需要更新最短路和次短路;后者解题策略是先统计出最短路径所经过的所有边,然后枚举所有经过的边,在去掉该边的情况下重新求出最短路径长度,并用ans记录重新求出的n个新图上最短路径长度中最小的那个,即为原图上的次短路径长度。对于本题,题目明确说明属于后者。注意,当最短路径不存在时,需要特判,此时次短路径一定不存在,输出 -1。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef long long ll;const int maxn = 1e5 + 6;
const int maxm = 1e5 + 6;struct edge
{int to;     // to为边的指向double len; // len为边的长度即边权
};vector<edge> e[maxn]; // 存储以点i为起点的边struct node
{double dis;                         // dis为目前到该点的最短路长度int num;                            // num为该点序号bool operator>(const node &a) const // 小根堆中的大于号重载{return dis > a.dis;}
};double minDis[maxn]; // 从起点到第i个点的最短路长度
bool vis[maxn];      // 第i个点是否已确定最短路长度
int pre[maxn];
int x, y; // 记录去掉的边的起点x和终点yvoid dijkstra(int n, int s) // n为点的个数,s为起点
{priority_queue<node, vector<node>, greater<node>> pq; // 还未确定最短路长度的点存放在小根堆中// 将最短路距离初始化为无穷大,vis初始化为0for (int i = 1; i <= n; i++){minDis[i] = 1e10;vis[i] = 0;}minDis[s] = 0.0; // 起点到起点的最短路长度为0pq.push({0, s});while (!pq.empty()){int u = pq.top().num; // 有向边的起点pq.pop();if (vis[u]) // 若该点已确定最短路长度,跳过continue;vis[u] = 1;for (edge eg : e[u]) // 遍历以该点为起点的所有有向边{int v = eg.to;if (x == u && y == v) // 遍历到去掉的边就跳过,从而找到次短路径continue;double w = eg.len;if (minDis[v] > minDis[u] + w) // 更新最短路长度{minDis[v] = minDis[u] + w;pre[v] = u; // 用pre记录最短路径中v的前驱upq.push({minDis[v], v});}}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);// 问题转化为求根1到各个结点的最短路径长度int n, m, s; // 点的个数,有向边的个数,出发点的编号cin >> n >> m;vector<pair<int, int>> a(n + 1); // 点的坐标for (int i = 1; i <= n; i++){cin >> a[i].first >> a[i].second;pre[i] = i;}s = 1; // 起点为根结点int u, v;double w;while (m--){cin >> u >> v;// 在读入无向边的过程中计算每条边的边权,即两点间距离w = sqrt(pow((a[u].first - a[v].first), 2) + pow((a[u].second - a[v].second), 2));e[u].push_back({v, w});e[v].push_back({u, w});}dijkstra(n, s);if (pre[n] == n) // 如果不存在最短路径,那么一定不存在次短路径{cout << -1 << '\n';return 0;}vector<pair<int, int>> path;int tmp = n;while (tmp != 1) // 通过从n向1遍历前驱,即可找出完整的路径{path.push_back({pre[tmp], tmp});tmp = pre[tmp];}double ans = 1e10;for (int i = 0; i < path.size(); i++) // 枚举路径上所有的边,统计去掉该边后的新图上最短路径长度的最小值{x = path[i].first;y = path[i].second;dijkstra(n, s);ans = min(ans, minDis[n]);}if (ans == 1e10) // 如果不存在次短路径,输出-1{cout << -1 << '\n';}else{cout << fixed << setprecision(2) << ans << '\n';}return 0;
}

相关文章:

VOJ 迷阵突围 题解 次短路径 dijkstra算法

迷阵突围 题目描述 小明陷入了坐标系上的一个迷阵&#xff0c;迷阵上有 n 个点&#xff0c;编号从 1 到 n 。小明在编号为 1 的位置&#xff0c;他想到编号为 n 的位置上。小明当然想尽快到达目的地&#xff0c;但是他觉得最短的路径可能有风险&#xff0c;所以他会选择第二短…...

Oracle SQL详解

Oracle SQL是一种用于管理和操作Oracle数据库的编程语言。以下是一些基本的Oracle SQL语法和建表建用户的详解。 创建用户 在Oracle中&#xff0c;创建用户通常需要具有足够权限的用户&#xff08;通常是具有DBA角色的用户&#xff09;。以下是一个创建用户的例子&#xff1a;…...

产业,到底需要什么大模型?

[ 产业究竟需要怎样的大模型&#xff1f;关于这个问题&#xff0c;本文作者便提出了他的看法&#xff0c;并总结了产业大模型目前阶段的三点落地挑战。一起来看看&#xff0c;或许可以帮助你更好地理解大模型与行业、与产业的融合。 写下这篇的起因&#xff0c;是前不久的一件事…...

每日5题Day17 - LeetCode 81 - 85

每一步向前都是向自己的梦想更近一步&#xff0c;坚持不懈&#xff0c;勇往直前&#xff01; 第一题&#xff1a;81. 搜索旋转排序数组 II - 力扣&#xff08;LeetCode&#xff09; class Solution {public boolean search(int[] nums, int target) {int n nums.length;if (n…...

后端开发面经系列 --中望C++面经

中望C面经&#xff0c;全部内容&#xff01; 公众号&#xff1a;阿Q技术站 文章目录 中望C面经&#xff0c;全部内容&#xff01;一面 8.15 时长45min1、介绍项目相关2、gdb怎么调试的&#xff1f;打断点用什么指令&#xff1f;3、gcc的编译过程4、cmake添加头文件搜索路径用…...

德国西门子论未来质量管理 - 如何与明天相遇?

未来制造业的质量 -- 如何用软件方案满足质量要求 作者&#xff1a;Bill Butcher 翻译&编辑&#xff1a;数字化营销工兵 【前言】在Frost&Sullivan最近发表的一份白皮书中&#xff0c;他们讨论了制造业的质量投资。质量是制造过程的关键要素&#xff0c;但似乎比其他…...

webpack快速入门---webpack的安装和基本使用

webpack是什么 本质上&#xff0c;webpack 是一个用于现代 JavaScript 应用程序的 静态模块打包工具。当 webpack 处理应用程序时&#xff0c;它会在内部从一个或多个入口点构建一个 依赖图(dependency graph)&#xff0c;然后将你项目中所需的每一个模块组合成一个或多个 bund…...

后端开发面经系列 -- 华为C++一面面经

HUAWEI – C一面面经 公众号&#xff1a;阿Q技术站 来源&#xff1a;https://www.nowcoder.com/feed/main/detail/b8113ff340d7444985b32a73c207c826 1、计网的协议分几层&#xff1f;分别叫什么&#xff1f; OSI七层模型 物理层 (Physical Layer): 负责物理设备之间的原始比…...

csrf漏洞与ssrf漏洞

环境&#xff1a;用kali搭建的pikachu靶场 一.CSRF 1.CSRF漏洞简介 跨站请求伪造&#xff08;CSRF&#xff09;漏洞是一种Web应用程序安全漏洞&#xff0c;攻击者通过伪装成受信任用户的请求来执行未经授权的操作。这可能导致用户在不知情的情况下执行某些敏感操作&#xff0…...

AWS EC2服务器开启root密码,SSH登录

1) EC2 Instance Connect连接&#xff0c;更改root密码 sudo passwd root 2&#xff09;接着切换到切换到 root 身份&#xff0c;编辑 SSH 配置文件 $ sudo -i$ vi /etc/ssh/sshd_configPasswordAuthentication no&#xff0c;把 no 改成 yes #PermitRootLogin prohibit-passw…...

常见代码版本管理工具

目录 一、引言 二、Gitee &#xff08;一&#xff09;优点与特点 &#xff08;二&#xff09;缺点 &#xff08;三&#xff09;使用报告 三、GitHub 四、SVN 五、总结 一、引言 在软件开发过程中&#xff0c;代码版本控制工具是不可或缺的。Gitee、GitHub和SVN是三种常…...

最新版点微同城源码34.7+全套插件+小程序前后端

带全套插件 自己耐心点配置一下插件 可以H5可以小程序 一款专属的同城服务平台对于企业和个人而言&#xff0c;无疑是拓展业务、提升服务品质的重要一环。点微同城源码搭配全套插件&#xff0c;以及完善的小程序前后端&#xff0c;将为您的业务发展提供强大支持 源码免费下载…...

逻辑回归及python实现

概述 logistic回归是一种广义线性回归&#xff08;generalized linear model&#xff09;&#xff0c;因此与多重线性回归分析有很多相同之处。它们的模型形式基本上相同&#xff0c;都具有 w‘xb&#xff0c;其中w和b是待求参数&#xff0c;其区别在于他们的因变量不同&#x…...

大模型押题高考语文作文,带着大模型参加语文高考会怎么样?

前沿 大语言模型通常是指那些经过大量数据训练,能够理解和生成自然语言文本的人工智能系统。这些模型通常具有数百万到数十亿个参数,能够执行多种语言任务,例如语言翻译、文本摘要、问答系统、文本生成等。大语言模型能够捕捉语言的复杂性和细微差别,提供更加准确和自然的…...

Linux Ext2/3/4文件系统

文章目录 前言一、Linux文件系统简介1.1 简介1.2 Linux File System Structure1.3 Directory Structure 二、Ext2/3/4文件系统2.1 Minix2.2 EXT2.3 EXT22.4 EXT32.5 EXT4 三、EXT Inode参考资料 前言 这篇文章介绍了Linux文件系统的一些基础知识&#xff1a;Linux 文件系统简介…...

SIMBA方法解读

目录 预处理scRNA-seqscATAC-seq 图构建&#xff08;5种场景&#xff09;scRNA-seq分析scATAC-seq分析多模态分析批次整合多模态整合 图学习SIMBA空间中查询实体识别TF-target genes 预处理 scRNA-seq 过滤掉在少于三个细胞中表达的基因。原始计数按文库大小标准化&#xff0…...

VueRoute url参数

版本 4.x 获取query参数 使用$router.query&#xff0c;可以获取参数对应的json对象。 获取url参数 需要在路由配置中定义。使用$router.param获取。...

WPS表格插件方方格子【凑数】功能:选出和等于固定数字的数

文章目录 后来发现可以下载方方格子插件&#xff0c;使用【凑数】功能https://ffcell.lanzouj.com/iwhfc1kjhayh【凑数】快速【凑数】 导师让沾发票&#xff0c;需要选出若干个数额的发票&#xff0c;使它们的和等于一个指定数。不知道怎么办了&#xff0c;查了一下&#xff0c…...

通过SpringCloudGateway中的GlobalFilter实现鉴权过滤

1.pom.xml中加入gateway jar包 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-gateway</artifactId></dependency> 2.创建权限过滤器 SecurityFilter /*** 鉴权过滤***/ Slf4j Component …...

TCP/IP(网络编程)

一、网络每一层的作用 &#xff0a;网络接口层和物理层的作用&#xff1a;屏蔽硬件的差异&#xff0c;通过底层的驱动&#xff0c;会提供统一的接口&#xff0c;供网络层使用 &#xff0a;网络层的作用&#xff1a;实现端到端的传输 &#xff0a;传输层:数据应该交给哪一个任…...

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

目录 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…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

qt+vs Generated File下的moc_和ui_文件丢失导致 error LNK2001

qt 5.9.7 vs2013 qt add-in 2.3.2 起因是添加一个新的控件类&#xff0c;直接把源文件拖进VS的项目里&#xff0c;然后VS卡住十秒&#xff0c;然后编译就报一堆 error LNK2001 一看项目的Generated Files下的moc_和ui_文件丢失了一部分&#xff0c;导致编译的时候找不到了。因…...

13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析

LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...

Linux操作系统共享Windows操作系统的文件

目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项&#xff0c;设置文件夹共享为总是启用&#xff0c;点击添加&#xff0c;可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download&#xff08;这是我共享的文件夹&#xff09;&…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...