A102289 雾港城的道路网 题解

题意简述

给定一棵带权无向图，图的节点有一个标高 (h[i])。你需要从起点 (S) 到终点 (T)，找到一条路径，使得路径上的标高满足：

• 路径的前半部分标高不下降（可以保持不变）。
• 路径的后半部分标高不再上升（可以保持不变）。

我们要求路径的总长度最小。

关键要求：

• “先不降，再不上升”是路径的标高约束，意味着路径的标高只能出现一次下降，且只能在某个位置发生转折。
• 求满足约束条件的最短路径。

---

解题思路

1. 路径标高约束的含义

• 标高的变化只有一个转折点，可以理解为先“上升”然后“下降”。
• 换句话说，路径上只允许标高变化从“升”到“降”一次。因此，我们需要找出一种方法，计算路径上符合这个条件的最短路径。

2. 分两步计算最短路径

考虑两次 Dijkstra 算法，分别计算符合条件的最短路径。

• 第一步：计算“上升路径”的最短路径
  从起点 (S) 开始，进行一次 Dijkstra 算法，在这次算法中，我们只允许沿着标高不下降的边（即 $(h[v] \ge h[u])$）进行路径搜索。
  该过程将得到从 (S) 到每个节点的最短路径，满足“标高不下降”的条件。

• 第二步：计算“下降路径”的最短路径
  从终点 (T) 开始，进行一次 Dijkstra 算法，允许沿着标高不升高的边（即 $(h[v] \le h[u])$）进行路径搜索。
  该过程将得到从 (T) 到每个节点的最短路径，满足“标高不升高”的条件。

3. 合并两部分路径

• 对于每一个节点 (k)，我们从 (S) 到 (k) 的路径是“上升路径”，从 (k) 到 (T) 的路径是“下降路径”。
• 如果 (k) 既在“上升路径”中可达且在“下降路径”中可达，则这条路径从 (S) 到 (T) 是合法的。

4. 计算最短路径

最终，合并这两部分路径的结果，通过计算从 (S) 到 (k) 的最短上升路径和从 (k) 到 (T) 的最短下降路径的和，找出最短的合法路径。

---

算法实现

#include <cstdio>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const ll INF=1e18;
int n,m,S,T;
vector<int> h;
vector<vector<pair<int,int>>> adj;
vector<ll> up,down;

void dijkstra_up(int s){
    up.assign(n+1,INF);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    up[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(d>up[u])continue;
        for(auto [v,w]:adj[u]){
            if(h[v]>=h[u]&&up[v]>d+w){
                up[v]=d+w;
                pq.push({up[v],v});
            }
        }
    }
}

void dijkstra_down(int t){
    down.assign(n+1,INF);
    priority_queue<pli,vector<pli>,greater<pli>> pq;
    down[t]=0;
    pq.push({0,t});
    while(!pq.empty()){
        auto [d,u]=pq.top();
        pq.pop();
        if(d>down[u])continue;
        for(auto [v,w]:adj[u]){
            if(h[v]<=h[u]&&down[v]>d+w){
                down[v]=d+w;
                pq.push({down[v],v});
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&S,&T);
    h.resize(n+1);
    for(int i=1;i<=n;i++)scanf("%d",&h[i]);
    adj.resize(n+1);
    for(int i=0;i<m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    dijkstra_up(S);   // 计算从 S 到所有点的上升路径
    dijkstra_down(T); // 计算从 T 到所有点的下降路径
    ll ans=INF;
    for(int k=1;k<=n;k++){
        if(up[k]!=INF&&down[k]!=INF)ans=min(ans,up[k]+down[k]);
    }
    printf("%lld\n",ans==INF?-1:ans);
    return 0;
}

---

代码分析

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) \log n))$，因此总时间复杂度为 $(O((n + m) \log n))$，可以处理 $(n \leq 200000)$ 的情况。

---

总结

这道题的核心是分两次 Dijkstra 算法计算路径，并根据路径上的标高变化进行条件判断。通过对每个点的前缀奇偶性进行计算，找到最短的合法路径。整体算法效率高，适合大规模输入。