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

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份

uva 10801(乘电梯dijkstra)

题意: 给几个电梯,电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析: 将进入第0层的电梯60s也算上,最后减。 坑点是如果target为0输出0。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algori

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin