luogu 2865 [USACO06NOV]路障Roadblocks (次短路 堆优化Dijkstra)

2024-03-20 12:48

本文主要是介绍luogu 2865 [USACO06NOV]路障Roadblocks (次短路 堆优化Dijkstra),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

贝茜把家搬到了一个小农场,但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景,不想那么快地结束她的旅途,于是她每次回农场,都会选择第二短的路径,而不象我们所习惯的那样,选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路,每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1,她的朋友们居住在农场N(即贝茜每次旅行的目的地)。 贝茜选择的第二短的路径中,可以包含任何一条在最短路中出现的道路,并且,一条路可以重复走多次。当然咯,第二短路的长度必须严格大于最短路(可能有多条)的长度,但它的长度必须不大于所有除最短路外的路径的长度。

输入输出格式

输入格式:

Line 1: Two space-separated integers: N and R

Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

 

输出格式:

Line 1: The length of the second shortest path between node 1 and node N

 

输入输出样例

输入样例#1:

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例#1:

450

说明

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

题目链接:https://www.luogu.org/problemnew/show/P2865

题目分析:由于同一个边可以走多次,故去掉vis数组的限制,求最短路的过程中同时记录最短路和次短路,注意更新时的条件,还要注意的是起点的次短路不是0!

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int const INF = 0x3fffffff;
int const MAXN = 5005;
int const MAXM = 1e5 + 5;
int n, m, dis[MAXN][2]; 
int cnt, head[MAXN];struct EDGE {int to, w, nxt;
}e[MAXM << 1];priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;void Init() {cnt = 0;memset(head, -1, sizeof(head));
}void Add(int u, int v, int w) {e[cnt].to = v;e[cnt].w = w;e[cnt].nxt = head[u];head[u] = cnt++;
}void SlackPath(int v, int newDis) {if (dis[v][0] > newDis) {dis[v][1] = dis[v][0];dis[v][0] = newDis;q.push(make_pair(newDis, v));} else if (dis[v][0] < newDis && newDis < dis[v][1]) {dis[v][1] = newDis;q.push(make_pair(newDis, v));}
}void HeapDijkstra(int v0) {for (int i = 1; i <= n; i++) {dis[i][0] = INF; dis[i][1] = INF;}dis[v0][0] = 0;q.push(make_pair(0, v0));while (!q.empty()) {int u = q.top().second;q.pop();for (int i = head[u]; i != -1; i = e[i].nxt) {int v = e[i].to;SlackPath(v, dis[u][0] + e[i].w);SlackPath(v, dis[u][1] + e[i].w);// printf("dis[%d][0] = %d  dis[%d][1] = %d\n", v, dis[v][0], v, dis[v][1]);}}
}int main() {Init();int u, v, w;scanf("%d %d", &n, &m);for (int i = 0; i < m; i++) {scanf("%d %d %d", &u, &v, &w);Add(u, v, w);Add(v, u, w);   }HeapDijkstra(1);printf("%d\n", dis[n][1]);
}

 

这篇关于luogu 2865 [USACO06NOV]路障Roadblocks (次短路 堆优化Dijkstra)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

从原理到实战解析Java Stream 的并行流性能优化

《从原理到实战解析JavaStream的并行流性能优化》本文给大家介绍JavaStream的并行流性能优化:从原理到实战的全攻略,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的... 目录一、并行流的核心原理与适用场景二、性能优化的核心策略1. 合理设置并行度:打破默认阈值2. 避免装箱

Python实战之SEO优化自动化工具开发指南

《Python实战之SEO优化自动化工具开发指南》在数字化营销时代,搜索引擎优化(SEO)已成为网站获取流量的重要手段,本文将带您使用Python开发一套完整的SEO自动化工具,需要的可以了解下... 目录前言项目概述技术栈选择核心模块实现1. 关键词研究模块2. 网站技术seo检测模块3. 内容优化分析模

Java实现复杂查询优化的7个技巧小结

《Java实现复杂查询优化的7个技巧小结》在Java项目中,复杂查询是开发者面临的“硬骨头”,本文将通过7个实战技巧,结合代码示例和性能对比,手把手教你如何让复杂查询变得优雅,大家可以根据需求进行选择... 目录一、复杂查询的痛点:为何你的代码“又臭又长”1.1冗余变量与中间状态1.2重复查询与性能陷阱1.

Python内存优化的实战技巧分享

《Python内存优化的实战技巧分享》Python作为一门解释型语言,虽然在开发效率上有着显著优势,但在执行效率方面往往被诟病,然而,通过合理的内存优化策略,我们可以让Python程序的运行速度提升3... 目录前言python内存管理机制引用计数机制垃圾回收机制内存泄漏的常见原因1. 循环引用2. 全局变

Python多线程应用中的卡死问题优化方案指南

《Python多线程应用中的卡死问题优化方案指南》在利用Python语言开发某查询软件时,遇到了点击搜索按钮后软件卡死的问题,本文将简单分析一下出现的原因以及对应的优化方案,希望对大家有所帮助... 目录问题描述优化方案1. 网络请求优化2. 多线程架构优化3. 全局异常处理4. 配置管理优化优化效果1.

MySQL中优化CPU使用的详细指南

《MySQL中优化CPU使用的详细指南》优化MySQL的CPU使用可以显著提高数据库的性能和响应时间,本文为大家整理了一些优化CPU使用的方法,大家可以根据需要进行选择... 目录一、优化查询和索引1.1 优化查询语句1.2 创建和优化索引1.3 避免全表扫描二、调整mysql配置参数2.1 调整线程数2.

深入解析Java NIO在高并发场景下的性能优化实践指南

《深入解析JavaNIO在高并发场景下的性能优化实践指南》随着互联网业务不断演进,对高并发、低延时网络服务的需求日益增长,本文将深入解析JavaNIO在高并发场景下的性能优化方法,希望对大家有所帮助... 目录简介一、技术背景与应用场景二、核心原理深入分析2.1 Selector多路复用2.2 Buffer

SpringBoot利用树形结构优化查询速度

《SpringBoot利用树形结构优化查询速度》这篇文章主要为大家详细介绍了SpringBoot利用树形结构优化查询速度,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一个真实的性能灾难传统方案为什么这么慢N+1查询灾难性能测试数据对比核心解决方案:一次查询 + O(n)算法解决

小白也能轻松上手! 路由器设置优化指南

《小白也能轻松上手!路由器设置优化指南》在日常生活中,我们常常会遇到WiFi网速慢的问题,这主要受到三个方面的影响,首要原因是WiFi产品的配置优化不合理,其次是硬件性能的不足,以及宽带线路本身的质... 在数字化时代,网络已成为生活必需品,追剧、游戏、办公、学习都离不开稳定高速的网络。但很多人面对新路由器

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、