【每日一题】小A的最短路
小A的最短路
https://ac.nowcoder.com/acm/problem/23482
题目
题目描述： 小A这次来到一个景区去旅游，景区里面有N个景点，景点之间有N-1条路径。
小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。
但是景区里面有两个景点比较特殊，它们之间是可以直接坐观光缆车通过，不需要消耗体力值。
而小A不想走太多的路，所以他希望你能够告诉它，从当前的位置出发到他想要去的那个地方，他最少要消耗的体力值是多少。
第一行一个整数N代表景区的个数。
接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。
接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。
接下来一行一个整数Q，表示有Q次询问。
接下来的Q行每行两个整数x,y代表小A的位置在x，而他想要去的地方是y。
对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力对于每个询问下x,y输出一个结果，代表x到y消耗的最少体力
解析
1）知识点
- 这道题是一道lcd板子题，但是我不会lcd，所以是现学现卖的（怕会写错了QAQ
2）看题目
- 这道题就是问你树上两点最短时间，然后一个特别的地方就是有一条路可以节省时间，求最短时间。
3）算法分析
- 我先来说一下lcd是啥：
- lcd就是用来查找树上两点之间的最近公共父节点的算法。我们这里为什么用呢，因为最短路肯定要有一个相交点，所以那个点就是最近的公共父节点。
- 然后我们就来解释一下lcd算法是什么原理吧：
- 首先我们要算两个点的最近公共父节点，这时假设节点一个高，一个低（前提是按照正常树的样子放好），公共父节点一定不会在他们之间。所以我们就先讲较低的节点上移到相同的层来。
- 然后就是查找父节点了，这个时候只要让两个节点同时不停的往上找（一边一下），那么迟早就找到了。
- 知道lcd是什么原理之后，我们再将怎么去实现这个算法，我们这里用的是在线算法：lcd+倍增。
- 首先是实现两个节点移动到相同的层数：我们理解一下可以发现，任何一个数都可以用不重复的二的倍数相加表示。然后我们就做一个循环，假设i的最大值为20，向下循环，这样算的也快呀hh
- 接下来就是同时查找父节点，就查呗。
- 最后我还有一个没有讲到的问题就是，深度和父节点怎么求：
- 深度用一个deep[]数组，然后父节点用一个f[][]数组就好了，第二个维度是什么？就是ta的第2^i个父节点（就是往上查找）。
4）算法操作
- 然后我们就来看一下算法代码：
- 数组初始化：
void dfs(int u, int fa) { deep[u] = deep[fa] + 1; for (int i = 0; i <= 20 - 1; i++) f[u][i + 1] = f[f[u][i]][i]; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].v; if (v == fa) continue; f[v][0] = u; dfs(v, u); } } - lca计算：
int lca(int x, int y) { if (deep[x] < deep[y]) swap(x, y); for (int i = 20; i >= 0; i--) if (deep[f[x][i]] >= deep[y]) x = f[x][i]; //将要计算的两个节点先换到同一层 //因为在换节点的时候，x一直在变，所有数字都可以拆成2的倍数之和（而且不重复），所以可以换到同一层 if (x == y) return x; for (int i = 20; i >= 0; i--) if (f[x][i] != f[y][i]) { x = f[x][i]; y = f[y][i]; } //将两个节点同时上移（同步移动）， return f[x][0]; } - 最后注意一下树的距离的计算：
int dist(int u, int v) { return deep[u] + deep[v] - 2 * deep[lca(u, v)]; }
5）打代码
- 打代码啦！
- 首先是用前向星保存树的结构
- 然后将数组初始化了
- 接下来就是计算最短距离了
- 因为有特殊道路，所以我们先算直通的
- 然后和使用这个路的时间去比大小
- 看我代码咯~
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区
const int N = 3e5 + 7;
int head[N], tot;
struct EDGE {
int u, v, w, next;
} edge[N << 1];
int deep[N], f[N][21];//节点深度，fa[i][j]为i的第2^j个祖先
//全局变量区
void init();//前向星初始化
void add_edge(int u, int v);//前向星加边
void dfs(int u, int fa);//前向星dfs
int lca(int x, int f);//搜索最近相同父节点
int dist(int u, int v);//求树两点的距离
//函数预定义区
int main() {
IOS;
int n; cin >> n;
init();
for (int i = 1; i <= n - 1; i++) {
int u, v; cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
int x, y; cin >> x >> y;
dfs(1, 0);
int T; cin >> T;
while (T--) {
int u, v; cin >> u >> v;
int ans = dist(u, v);//初始化为直接路径
ans = min(ans, dist(u, x) + dist(y, v));
ans = min(ans, dist(u, y) + dist(x, v));
//判断要不要去走近路
cout << ans << endl;
}
return 0;
}
void init() {
memset(head, 0, sizeof head); tot = 0;
}
void add_edge(int u, int v) {
tot++;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
deep[u] = deep[fa] + 1;
for (int i = 0; i <= 20 - 1; i++)
f[u][i + 1] = f[f[u][i]][i];
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (v == fa) continue;
f[v][0] = u;
dfs(v, u);
}
}
int lca(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
for (int i = 20; i >= 0; i--)
if (deep[f[x][i]] >= deep[y])
x = f[x][i];
//将要计算的两个节点先换到同一层
//因为在换节点的时候，x一直在变，所有数字都可以拆成2的倍数之和（而且不重复），所以可以换到同一层
if (x == y) return x;
for (int i = 20; i >= 0; i--)
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
//将两个节点同时上移（同步移动），
return f[x][0];
}
int dist(int u, int v) {
return deep[u] + deep[v] - 2 * deep[lca(u, v)];
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
