题解：P15619 [ICPC 2022 Jakarta R] City Hall

· · 题解

问题重述

给定一个无向连通图，每个点有一个初始海拔 h_i。边 (x,y) 的权值为 (h_x-h_y)^2。
你可以将至多一个点的海拔改为任意非负实数，求从 s 到 t 的最短路径，绝对误差不超过 10^{-6}。

解题思路

1. 预处理原图最短路

在未修改时，边权非负，因此可以用 Dijkstra 求出：

原图的最短路为 a[t]，作为答案的一种情况。

2. 考虑修改一个点后的影响

设我们修改点 i，将其海拔改为 w (x\ge 0)。
若最优路径经过点 i，则它可表示为：

s\to\cdots\to x\to i\to y\to\cdots\to t

其中 x 和 y 是 i 的两个邻居，则该路径的总能量为：

a[x]+(h_x-w)^2+(w-h_y)^2 + b[y]

由于边权非负，任何最优路径都可以写成这种分解形式（若 a[x] 或 b[y] 经过 i，可作简单剪枝，不会使答案更差）。

对固定的 x,y，关于 x 的二次函数 (h_x-w)^2+(w-h_y)^2 的最小值在 w=\dfrac{h_x+h_y}{2} 处取得，最小值为：\frac{(h_x-h_y)^2}{2}

因此，修改点 i 后，经过 i 的最优能量为：

\min_{x,y\in N(i)}\left\{a[x]+b[y]+\frac{(h_x-h_y)^2}{2}\right\} \tag{1}

其中 N(i) 表示 i 的邻居集合。

最终答案还需与 a[t] 取最小值。

3. 李超线段树优化

由于直接枚举所有点 i 以及其所有邻居对 x,y 的复杂度可能达到 \sum deg(i)^2，最坏情况下无法接受。所以我们需要用李超线段树进行快速查询。

复杂度分析

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e6+10;
const long long inf=4e18;
typedef long long ll;
typedef pair<ll,int> PLI;
vector<int> q[N];
ll a[N],b[N],h[N],maxn,ans;
int vis[N],idx,cnt,tr[4*N],ver[4*N],cur;
struct node{
    ll k,b;
}q1[4*N];
void dijkstra(int s,int t){
    priority_queue<PLI,vector<PLI>,greater<PLI> > p;
    memset(a,0x3f,sizeof a);
    memset(b,0x3f,sizeof b);
    a[s]=0,p.push({0,s});
    while(!p.empty()){
        ll dis=p.top().first;
        int x=p.top().second;
        p.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int y:q[x]){
            ll w=dis+(h[x]-h[y])*(h[x]-h[y]);
            if(w<a[y]){
                a[y]=w;
                p.push({w,y});
            }
        }
    }
    b[t]=0,p.push({0,t});
    memset(vis,0,sizeof vis);
    while(!p.empty()){
        ll dis=p.top().first;
        int x=p.top().second;
        p.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int y:q[x]){
            ll w=dis+(h[x]-h[y])*(h[x]-h[y]);
            if(w<b[y]){
                b[y]=w;
                p.push({w,y});
            }
        }
    }
}
inline void insert(ll k,ll b){
    q1[++cnt]={k,b}; 
}
inline ll cal(int x,ll t){
    if(!x) return inf;
    return q1[x].k*t+q1[x].b;
}
void modify(int x,int l,int r,int t){
    if(ver[x]!=cur){
        ver[x]=cur;
        tr[x]=t;
        return;
    }
    if(l==r){
        if(cal(t,l)<cal(tr[x],l)) tr[x]=t;
        return;
    }
    int mid=l+r>>1;
    if(cal(t,mid)<cal(tr[x],mid)) swap(tr[x],t);
    if(cal(t,l)<cal(tr[x],l)) modify(x*2,l,mid,t);
    else if(cal(t,r)<cal(tr[x],r)) modify(x*2+1,mid+1,r,t); 
}
ll query(int x,int l,int r,ll t){
    if(r<t||l>t||ver[x]!=cur) return inf;
    if(l==r) return cal(tr[x],t);
    int mid=(l+r)>>1;
    ll res=cal(tr[x],t);
    if(t<=mid) res=min(res,query(x*2,l,mid,t));
    else res=min(res,query(x*2+1,mid+1,r,t));
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,s,t,x,y;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        maxn=max(maxn,h[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        q[x].push_back(y);
        q[y].push_back(x);
    } 
    dijkstra(s,t);
    ans=a[t];
    for(int x:q[s]) ans=min(ans,b[x]);
    for(int x:q[t]) ans=min(ans,a[x]);
    ans*=2;
    for(int x=1;x<=n;x++){
        cnt=0,cur++;
        for(int y:q[x]){
            ll k=-2*h[y],b=2*a[y]+h[y]*h[y];
            insert(k,b);
            modify(1,0,maxn,cnt);
        }
        for(int y:q[x]){
            ll w=query(1,0,maxn,h[y]);
            if(w<inf){
                w+=2*b[y]+h[y]*h[y];
                ans=min(ans,w);
            }
        }
    }
    cout<<fixed<<setprecision(6)<<ans/2.0;
    return 0;
}