题目描述

给定一个仙人掌图，求两个点间的最短路

算法

有别于其他神仙写的圆方树，这里使用了一种其他的方法，但和圆方树很类似
这里的建图方式是：把1号节点作为根，环上的点都接到最浅的节点上，不在环上的不变
用dis表示从1到每个节点的最短路
用g表示在dfs树上1到每个节点的距离
对于两个点x,y （假设x比y深）
如果y是x的祖先 答案就是dis[x]-dis[y]
如果lca不在环上，那答案就是dis[x]+dis[y]-2*d[lca]
如果lca在环上，
设x到环上距离最近的点是fx，y到环上距离最近的点是fy，环的总长度是sum
那么答案就是 min(abs(g[fx]-g[fy]),sum-abs(g[fx]-g[fy]))+dis[x]-dis[fx]+dis[y]-dis[fy];
另外本题细节一堆

时间复杂度

O(nlogn+qlogn) (口胡的)

参考

https://www.luogu.com.cn/blog/a23333/post-mu-ban-jing-tai-xian-ren-zhang

C++ 代码

#include<bits/stdc++.h>
#define ll long long
#define make(aa,bb) make_pair(aa,bb) 
#define PII pair<int,int>
#define fi first
#define se second
#define lowbit(x) x&-x
using namespace std;
const int N=1e4+5,M=8e4+5;
int n,m,T,t,cnt;
int tot=1,head[M],ver[M],w[M],Next[M];
int f[N][16],dis[N],cs[N],pre[N],g[N],sum[M],v[M],id[N];
bool bj[N];
void add(int x,int y,int z){
    ver[++tot]=y,w[tot]=z,Next[tot]=head[x],head[x]=tot;
}
void spfa(){
    queue<int> q;q.push(1);
    memset(dis,0x3f,sizeof(dis));dis[0]=dis[1]=0;
    while(q.size()){
        int x=q.front();q.pop();bj[x]=0;
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],z=w[i];
            if(dis[y]>dis[x]+z) {
                dis[y]=dis[x]+z;
                if(!bj[y]) bj[y]=1,q.push(y);
            }
        }
    }
}
void dfs1(int x,int root){
    //printf("%d %d %d\n",x,root,pre[x]);
    if(x==root) return;
    add(root,x,0);add(x,root,0);
    v[pre[x]]=v[pre[x]^1]=1;
    sum[cnt]+=w[pre[x]];
    id[x]=cnt;
    dfs1(ver[pre[x]^1],root);
}
void dfs0(int x,int pr){
    //cout<<x<<endl;
    cs[x]=++t;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i],z=w[i];
        if(y==pr) continue;
        if(!cs[y]) pre[y]=i,g[y]=g[x]+z,dfs0(y,x);
        else if(cs[y]<cs[x]){
            sum[++cnt]=z;
            v[i]=v[i^1]=1;dfs1(x,y);
        }
    }
}
void dfs2(int x,int pr){
    for(int i=1;i<=14;i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i],z=w[i];
        if(v[i]||y==pr) continue;
        cs[y]=cs[x]+1;f[y][0]=x;
        dfs2(y,x);
    }
}
int solve(){
    int x,y;scanf("%d%d",&x,&y);
    if(cs[x]<cs[y]) swap(x,y);
    int a=x,b=y;
    for(int i=14;i>=0;i--){
        if(cs[f[x][i]]>=cs[y]) x=f[x][i];
    }
    if(x==y) return dis[a]-dis[b];
    for(int i=14;i>=0;i--){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    if(id[x]&&id[x]==id[y]){
        int tmp=abs(g[x]-g[y]);
        return min(tmp,sum[id[x]]-tmp)+dis[a]-dis[x]+dis[b]-dis[y];
    }
    return dis[a]+dis[b]-2*dis[f[x][0]];
}
int main(){
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=m;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    spfa();
    dfs0(1,0);
    //cout<<"A\n";
    memset(cs,0,sizeof(cs));
    dfs2(1,0);
    while(T--) printf("%d\n",solve());
    return 0;
}