【图论经典题目讲解】洛谷 P2149 Elaxia的路线

2024-02-16 09:36

本文主要是介绍【图论经典题目讲解】洛谷 P2149 Elaxia的路线,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P2149 Elaxia的路线

D e s c r i p t i o n \mathrm{Description} Description

给定 n n n 个点, m m m 条边的无向图,求 2 2 2 个点对间最短路的最长公共路径

S o l u t i o n \mathrm{Solution} Solution

最短路有可能不唯一,所以公共路径的长度就有可能不同。

2 2 2 条最短路都会经过的边(包括同向和异向)记录出来,并建立 1 1 1 个新图,那么由于最短路(可以看做一条链)一定不会走环,故新图必定是一个 有向无环图 (简称 D A G \mathrm{DAG} DAG),而 D A G \mathrm{DAG} DAG 图上就可以跑 DP 来求解最长链,由于找出的是 2 2 2 条最短路都经过的边,所以最长链其实就是 2 2 2 条最短路的最长公共路径。

故,该问题得以解决。

C o d e Code Code

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;
typedef long long LL;const int SIZE = 1e6 + 10;int N, M;
int X1, Y1, X2, Y2;
int h[SIZE], hs[SIZE], e[SIZE], ne[SIZE], w[SIZE], idx;
int D[4][SIZE], Vis[SIZE], in[SIZE], q[SIZE], hh, tt = -1;
int F[SIZE];void add(int h[], int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}void Dijkstra(int Start, int dist[])
{for (int i = 1; i <= N; i ++)dist[i] = 1e18, Vis[i] = 0;priority_queue<PII, vector<PII>, greater<PII>> Heap;Heap.push({0, Start}), dist[Start] = 0;while (Heap.size()){auto Tmp = Heap.top();Heap.pop();int u = Tmp.second;if (Vis[u]) continue;Vis[u] = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (dist[j] > dist[u] + w[i]){dist[j] = dist[u] + w[i];Heap.push({dist[j], j});}}}
}void Topsort()
{hh = 0, tt = -1;for (int i = 1; i <= N; i ++)if (!in[i])q[ ++ tt] = i;while (hh <= tt){int u = q[hh ++];for (int i = hs[u]; ~i; i = ne[i]){int j = e[i];if ((-- in[j]) == 0)q[ ++ tt] = j;}}
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);memset(h, -1, sizeof h);memset(hs, -1, sizeof hs);cin >> N >> M >> X1 >> Y1 >> X2 >> Y2;int u, v, c;while (M --){cin >> u >> v >> c;add(h, u, v, c), add(h, v, u, c);}Dijkstra(X1, D[0]), Dijkstra(Y1, D[1]);Dijkstra(X2, D[2]), Dijkstra(Y2, D[3]);for (int i = 1; i <= N; i ++)for (int j = h[i]; ~j; j = ne[j]){int k = e[j];if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[2][i] + w[j] + D[3][k] == D[2][Y2])add(hs, i, k, w[j]), in[k] ++;}Topsort();for (int it = 0; it <= tt; it ++){int i = q[it];for (int j = hs[i]; ~j; j = ne[j]){int k = e[j];F[k] = max(F[k], F[i] + w[j]);}}int Result = 0;for (int i = 1; i <= N; i ++)Result = max(Result, F[i]);memset(hs, -1, sizeof hs);memset(F, 0, sizeof F);memset(in, 0, sizeof in);for (int i = 1; i <= N; i ++)for (int j = h[i]; ~j; j = ne[j]){int k = e[j];if (D[0][i] + w[j] + D[1][k] == D[0][Y1] && D[3][i] + w[j] + D[2][k] == D[2][Y2])add(hs, i, k, w[j]), in[k] ++;//, cout << i << " " << k << endl;}Topsort();for (int it = 0; it <= tt; it ++){int i = q[it];for (int j = hs[i]; ~j; j = ne[j]){int k = e[j];F[k] = max(F[k], F[i] + w[j]);}}for (int i = 1; i <= N; i ++)Result = max(Result, F[i]);cout << Result << endl;return 0;
}

这篇关于【图论经典题目讲解】洛谷 P2149 Elaxia的路线的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

Java进程CPU使用率过高排查步骤详细讲解

《Java进程CPU使用率过高排查步骤详细讲解》:本文主要介绍Java进程CPU使用率过高排查的相关资料,针对Java进程CPU使用率高的问题,我们可以遵循以下步骤进行排查和优化,文中通过代码介绍... 目录前言一、初步定位问题1.1 确认进程状态1.2 确定Java进程ID1.3 快速生成线程堆栈二、分析

javascript fetch 用法讲解

《javascriptfetch用法讲解》fetch是一个现代化的JavaScriptAPI,用于发送网络请求并获取资源,它是浏览器提供的全局方法,可以替代传统的XMLHttpRequest,这篇... 目录1. 基本语法1.1 语法1.2 示例:简单 GET 请求2. Response 对象3. 配置请求

Java Stream.reduce()方法操作实际案例讲解

《JavaStream.reduce()方法操作实际案例讲解》reduce是JavaStreamAPI中的一个核心操作,用于将流中的元素组合起来产生单个结果,:本文主要介绍JavaStream.... 目录一、reduce的基本概念1. 什么是reduce操作2. reduce方法的三种形式二、reduce

CSS引入方式和选择符的讲解和运用小结

《CSS引入方式和选择符的讲解和运用小结》CSS即层叠样式表,是一种用于描述网页文档(如HTML或XML)外观和格式的样式表语言,它主要用于将网页内容的呈现(外观)和结构(内容)分离,从而实现... 目录一、前言二、css 是什么三、CSS 引入方式1、行内样式2、内部样式表3、链入外部样式表四、CSS 选

Git可视化管理工具(SourceTree)使用操作大全经典

《Git可视化管理工具(SourceTree)使用操作大全经典》本文详细介绍了SourceTree作为Git可视化管理工具的常用操作,包括连接远程仓库、添加SSH密钥、克隆仓库、设置默认项目目录、代码... 目录前言:连接Gitee or github,获取代码:在SourceTree中添加SSH密钥:Cl

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.