[模板]静态仙人掌

· · 题解

没有用圆方树，不过本质差不太多。

目前最优解，可能很快就不是了

建图方式： 对于一个环，就把所有环上的点接到环上深度最低的那个点上面去。然后就是一颗树了。

然后 dis表示从 1 到 x 的最短距离，SPFA 求出。建树之前求出。

然后 Dis 表示建树之前，1 到 x在 dfs 树上的距离。这个是为了能快速求环上两点之间的距离。

然后建树，倍增。

首先先对于询问 x,y ，如果 lca 是 x 或者y 就返回 dis[x]-dis[y]

否则如果 lca(x,y) 不是环上的点，就是 dis[x]+dis[y]-2*dis[lca]

否则就是环上的情况。

因为倍增的时候判的是深度，而一个环上深度一样。

对了还要维护每个点属于那个环，还有每个环的环长。然后就有两种走法，返回最小值就行了。

细节好像还挺多的，也不是很好实现。不过代码不长。

代码：

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
#define N 10005
#define M 80005
using namespace std;

inline void rd(int &X){
    X=0;char ch=0;
    while(!isdigit(ch))ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
}

int n,m,q,cnt=1,tot,num;
int head[N],dis[N],v[N];
struct nd{int nxt,to,v;}e[M];
int d[N],Dis[N],vis[M],pre[N],sum[M],c[N],f[N][15];
#define For(x) for(int y,i=head[x];(y=e[i].to);i=e[i].nxt)

inline void add(int x,int y,int v){
    e[++cnt]={head[x],y,v};head[x]=cnt;
    e[++cnt]={head[y],x,v};head[y]=cnt;
}

void SPFA(){
    queue<int> q;q.push(1);
    memset(dis,0x3f,sizeof dis);dis[1]=dis[0]=0;
    while(q.size()){
        int x=q.front();q.pop();v[x]=0;
        For(x) if(dis[y]>dis[x]+e[i].v){
            dis[y]=dis[x]+e[i].v;
            if(!v[y]) v[y]=1,q.push(y);
        }
    }
}
void work(int x,int rt){
    if(x==rt) return ;
    add(rt,x,0);vis[pre[x]]=vis[pre[x]^1]=1;
    sum[num]+=e[pre[x]].v;c[x]=num;work(e[pre[x]^1].to,rt);
}
void dfs(int x){
    v[x]=++tot;
    For(x) if(i^pre[x]^1)
        if(!v[y]) pre[y]=i,Dis[y]=Dis[x]+e[i].v,dfs(y);
        else if(v[y]<v[x]) {
            sum[++num]=e[i].v;
            vis[i]=vis[i^1]=1; work(x,y);
        }
}
void dfs2(int x){
    for(int i=1;i<=14;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    For(x) if(!vis[i] and y!=f[x][0])
        d[y]=d[x]+1,f[y][0]=x,dfs2(y);
}
int ask(int x=0,int y=0){
    rd(x);rd(y);
    if(d[x]<d[y]) swap(x,y);
    int X=x,Y=y;
    for(int i=14;~i;i--)
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    if(x==y) return dis[X]-dis[Y];
    for(int i=14;~i;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    if(c[x] and c[x]==c[y]){
        int now=sum[c[x]],L=abs(Dis[x]-Dis[y]);
        return min(L,now-L)+dis[X]-dis[x]+dis[Y]-dis[y];
    }return dis[X]+dis[Y]-2*dis[f[x][0]];
}
signed main(){
    rd(n);rd(m);rd(q);
    for(int x,y,v,i=1;i<=m;i++)
        rd(x),rd(y),rd(v),add(x,y,v);
    SPFA();dfs(1);dfs2(1);
    while(q--) printf("%d\n",ask());
}