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

2024-06-07 01:36

本文主要是介绍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算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1037816

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1