首页 > 试题广场 >

小A的最短路

[编程题]小A的最短路

时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。

输入描述:

第一行一个整数N代表景区的个数。
接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。
接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。
接下来一行一个整数Q，表示有Q次询问。
接下来的Q行每行两个整数x,y,代表小A的位置在x，而他想要去的地方是y。

输出描述:

示例1

输入

输出

1
0

备注:

算法知识视频讲解

CoolGuang!

发表于 2020-07-31 13:03:41

首先题目给出是一棵树我们可以知道树上两点路径唯一其次又有一条额外免费的边所以我们可以这么考虑，x,y之间的路径要么是在原树上由x到y，要么经过额外免费的边对于每个询问，取三种情况最小值即可 ll n,m,p; struct node{ int e,next; }edge[maxn] 展开全文

lifehappy

发表于 2020-07-31 15:15:25

小A的最短路思路树上问题求两个点的最短距离，显然能用来进行的查询，引入了两个无边权的点，所以我们的路劲就可以规划成三种，只要在这三个当中取一个最小值就行了。接下来就是考虑求了，有一种较为快速的求的在线方法，那就是树链剖分，于是套上去(个人认为树剖求较为好写)，然后就可以开始最短路求解了。代码展开全文

东溪看水

发表于 2020-08-12 17:47:03

题目小A这次来到一个景区去旅游，景区里面有 N 个景点，景点之间有 N-1 条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去展开全文

程序蒟蒻

发表于 2020-08-17 18:41:54

思路：如果没有缆车的话，就是一个利用LCA求树上任意两点距离的板子题。（有了缆车，其实还是板子题……）有了一个缆车之后，无非就算考虑一下要不要坐缆车以及怎样坐缆车，所以：不坐缆车xy的距离就是原来的距离dist(x,y)，坐缆车的话要考虑是x到u点坐缆车，还是到v点坐缆车，即dist(x, 展开全文

hnust_yangyanjun

发表于 2020-08-09 21:55:30

题意：有一颗n个节点的树，经过一条边消耗一点体力。有两个特殊点之间有一个观光缆车，他们之间不需要消耗体力。有Q个询问，每个询问求从x点到y点消耗体力值最少为多少？思路：求任意两点树上的距离应该用LCA.由于多了个电缆，所以我们从x到y是有3种方案：①从x直接到y，不坐电缆。②从x到u，再从u坐电缆展开全文

sunrise__sunrise

发表于 2020-07-31 13:50:21

题面大意 Solution #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include < 展开全文

blowhail

发表于 2020-08-07 18:05:01

先不看线缆，会发现，直接用lca求最短路就行了加上线缆，就多加一个判断即可比如询问x到y，线缆是j到k在dis(x,y)，dis(x,j)+dis(k,y)，dis(x,k)+dis(j,y)这三个中取最小 #include <cstdio> #include <iostream& 展开全文

昵称很长很长真是太好了

发表于 2020-07-31 16:25:46

题目描述：小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那展开全文

wwt_001

发表于 2020-08-06 20:34:23

题意：给你一棵树包含n个顶点，和n-1条边。在这棵树的基础上再加一条边。求树上两个顶点之间的距离。题解：其实有题意我们很容易想到要求两个顶点之间的LCA,从而间接求解两个顶点之间的最短距离。1.首先我们考虑不做缆车，那就是求dist(x,y)2.我们在考虑做缆车的情况，但是有分两种情况2.1从x走展开全文

998244353

发表于 2020-07-31 16:59:18

题意：给定一棵个点的树，边权均为，以及多出的一条边权为的边，询问树上两点之间的路径的最小权值。题解： https://ac.nowcoder.com/acm/problem/19814 这道题的弱化版，只多出了一条边权为的边。预处理树上倍增关系，然后加入这条边权为边，每次取直接在树上走的最短路权展开全文

问题信息

枚举

难度：

0条回答 0收藏 10浏览

小A的最短路

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题