首页 > 其他分享 >[POI2007] [LUOGU P3451]旅游景点 Tourist Attractions

[POI2007] [LUOGU P3451]旅游景点 Tourist Attractions

时间:2024-04-07 20:55:25浏览次数:27  
标签:Tourist 包含 LUOGU POI2007 样例 道路 FGD 城市

本题解由于作者太菜在POI及LUOGU上会TLE,该题解主要讲思路,剩下的内存优化请各位大佬自行补充,欢迎评论区讨论
本题解运行时间10406 ms,空间194584 KiB

题目描述

FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD

不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的,他可以在某些旅行方案之间进行选择。由

于FGD非常讨厌乘车的颠簸,他希望在满足他的要求的情况下,旅行的距离尽量短,这样他就有足够的精力来欣赏风景或者是泡MM了_. 整个城市交通网络包含N个城

市以及城市与城市之间的双向道路M条。城市自1至N依次编号,道路亦然。没有从某个城市直接到它自己的道路,两个城市之间最多只有一条道路直接相连,但可以有

多条连接两个城市的路径。任意两条道路如果相遇,则相遇点也必然是这N个城市之一,在中途,由于修建了立交桥和下穿隧道,道路是不会相交的。每条道路都有一个

固定长度。在中途,FGD想要经过K(K<=N-2)个城市。成都编号为1,上海编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1. 举例来说,假设交通网络如下图。

FGD想要经过城市2,3,4,5,并且在2停留的时候在3之前,而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为19。注意FGD为了从城市2到城市4

可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径,因此这个方案正是FGD需要的。

输入格式

第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。以下M行,每行包含3个整数X,y,z,(1<=x,y<=n,0<z<=1000);

接下来一行,包含一个整数q,表示有q个限制条件(0<=q<n)。以下q行,每行两个整数f,l(1<=l,f<=n),表示在f停留的时候要在l之前。

输出格式

只包含一行,包含一个整数,表示最短的旅行距离。

样例

样例输入

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

样例输出

19

调了4天,经历了87次失败才调出来,但内存很大,只能在HZOI上过,原题80分。。。还是太菜了

记录一下这历史性的一刻;

image
image
image
image

题解

标签:Tourist,包含,LUOGU,POI2007,样例,道路,FGD,城市
From: https://www.cnblogs.com/PeppaEvenPig/p/18119857

相关文章

  • luoguP1024-二分
    题目链接实数二分:实数二分不存在边界问题,二分时可以设立循环次数或确立精度1.若存在2个数x1和x2,且x1<x2,f(x1)×f(x2)<0之间一定存在它的一个浮点数根2.且题目给定实根范围在-100~100之间,按位枚举方程=0时,显然x是方程的一个整数实根题目描述有形如:ax3+bx2+cx+d=0这样......
  • luoguP1102-双指针
    题目链接:P1102A-B数对-洛谷|计算机科学教育新生态(luogu.com.cn)利用单调性求解双指针解法:排序构造出区间单调,则若存在目标值B,B在序列中一定为连续区间,此时通过双指针l和r,此时维护一段区间:有S[L]大于S[I]-C,S[R]大于等于S[I]-C,此时我们枚举每一位,若存在A......
  • Luogu P8710 [蓝桥杯 2020 省 AB1] 网络分析 题解 [ 绿 ] [ 带权并查集 ]
    原题分析本题由于从一个节点发信息,同一个集合内的所有点都会收到信息,显然是一道要求维护各节点间关系的题,因此采用并查集的数据结构进行求解。但由于维护关系的同时还要维护权值,所以采用带权并查集,它是一种能维护某个节点与其祖宗节点之间关系的数据结构。带权并查集找父亲的......
  • Luogu P3294 背单词
    观前须知本题解全部内容遵循CCBY-NC-SA4.0Deed原则同步发布于Luogu题解区更好的观看体验点这里笔者的博客主页正文LuoguP3294【SCOI2016】背单词笔者在刷题的时候看到了这道好题花了四十分钟切掉以后,看了一下题解发现自己的想法不太一样所以想做一篇适合我这样的......
  • 旅游景点 Tourist Attractions
    [POI2007]ATR-TouristAttractions题目背景FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下......
  • luogu P1543 [POI2004] SZP 题解
    题目传送门前置知识树形DP解法将\(a_{i}\)向\(i\)连一条有向边,这样就形成了基环外向树森林。基环外向树森林内每棵基环外向树是相互独立的,需要单独处理。对于每棵基环外向树,任取环上一点\(x\),断开\(x\)到\(fa_{x}\)的有向边,外向树就变成了一棵以\(x\)为根的树。......
  • Luogu P6834 梦原 题解
    原题传送门首先考虑如果树的形态确定了之后的情况:如果当前点比爸爸的值大,那么显然爸爸变成\(0\)之后,这个点需要自己被额外操作删除,贡献就是\(a[v]-a[u]\)。类似,如果比爸爸的值小,那么这个点肯定会跟爸爸一起被删除,所以贡献就是\(0\)。综上所述,一个点的贡献是\(max{a[v]-......
  • luogu6801题解
    本题解中不区别长度和宽度的区别,它们在本题解中指的是同一个东西。本题解做法用到单调栈。看这个特殊性质好像是让我们在高度上进行研究一下。子任务\(4\)的特殊性质是想让你搞明白在一个矩形中如何计算其内部的矩形个数。下面是一个\(4\times5\)大小的矩形。先来不考......
  • luoguP3330 [ZJOI2011] 看电影--组合数学--高精度
    \(luoguP3330\)[ZJOI2011]看电影废了老命想题解$$luogu$$$$HZOI$$题意到了难得的假期,小白班上组织大家去看电影。但由于假期里看电影的人太多,很难做到让全班看上同一场电影。最后大家在一个偏僻的小胡同里找到了一家电影院,但这家电影院分配座位的方式很特殊,具体方式如......
  • 3101: *【莫比乌斯反演:练习】gcd(i,j)=k的对数[POI2007]ZAP-Queries
    问题给出\(n,m,k\)(\(1\leqn,m,k\leq10^5\)),求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\lbrack\gcd(i,j)=k\rbrack\),即:满足\(1\leqi\leqn\),\(1\leqj\leqm\),且\(\gcd(i,j)=k\)的二元组\((i,j)\)的数量。题解\(\sum\limits_{i=1}......