A102289 雾港城的道路网 题解
题意简述
给定一棵带权无向图，图的节点有一个标高 (h[i])。你需要从起点 (S) 到终点 (T)，找到一条路径，使得路径上的标高满足：
* 路径的前半部分标高不下降（可以保持不变）。
* 路径的后半部分标高不再上升（可以保持不变）。
我们要求路径的总长度最小。
关键要求：
* “先不降，再不上升”是路径的标高约束，意味着路径的标高只能出现一次下降，且只能在某个位置发生转折。
* 求满足约束条件的最短路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
1. 路径标高约束的含义
* 标高的变化只有一个转折点，可以理解为先“上升”然后“下降”。
* 换句话说，路径上只允许标高变化从“升”到“降”一次。因此，我们需要找出一种方法，计算路径上符合这个条件的最短路径。
2. 分两步计算最短路径
考虑两次 Dijkstra 算法，分别计算符合条件的最短路径。
* 第一步：计算“上升路径”的最短路径
从起点 (S) 开始，进行一次 Dijkstra 算法，在这次算法中，我们只允许沿着标高不下降的边（即 (h[v]≥h[u])(h[v] \ge h[u])(h[v]≥h[u])）进行路径搜索。
该过程将得到从 (S) 到每个节点的最短路径，满足“标高不下降”的条件。
* 第二步：计算“下降路径”的最短路径
从终点 (T) 开始，进行一次 Dijkstra 算法，允许沿着标高不升高的边（即 (h[v]≤h[u])(h[v] \le h[u])(h[v]≤h[u])）进行路径搜索。
该过程将得到从 (T) 到每个节点的最短路径，满足“标高不升高”的条件。
3. 合并两部分路径
* 对于每一个节点 (k)，我们从 (S) 到 (k) 的路径是“上升路径”，从 (k) 到 (T) 的路径是“下降路径”。
* 如果 (k) 既在“上升路径”中可达且在“下降路径”中可达，则这条路径从 (S) 到 (T) 是合法的。
4. 计算最短路径
最终，合并这两部分路径的结果，通过计算从 (S) 到 (k) 的最短上升路径和从 (k) 到 (T) 的最短下降路径的和，找出最短的合法路径。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
算法实现
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码分析
1. 数据结构：
* adj：邻接表，用于存储图的边。
* up：存储从起点 (S) 到每个节点的最短路径，路径上的标高不下降。
* down：存储从终点 (T) 到每个节点的最短路径，路径上的标高不上升。
2. 算法：
* 使用 Dijkstra 算法计算最短路径：
* dijkstra_up(S)：计算从起点 (S) 出发，满足标高不下降的最短路径。
* dijkstra_down(T)：计算从终点 (T) 出发，满足标高不上升的最短路径。
3. 结果计算：
* 遍历所有节点 (k)，计算从 (S) 到 (k) 的最短上升路径和从 (k) 到 (T) 的最短下降路径的和，最终得到最短合法路径。
4. 时间复杂度：
每次 Dijkstra 算法的时间复杂度为 (O((n+m)logn))(O((n + m) \log n))(O((n+m)logn))，因此总时间复杂度为 (O((n+m)logn))(O((n + m) \log n))(O((n+m)logn))，可以处理 (n≤200000)(n \leq 200000)(n≤200000) 的情况。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
这道题的核心是分两次 Dijkstra 算法计算路径，并根据路径上的标高变化进行条件判断。通过对每个点的前缀奇偶性进行计算，找到最短的合法路径。整体算法效率高，适合大规模输入。
