BZOJ2125: 最短路(圆方树)

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q;
struct Edge {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge){x, y, z, head[x]};
    head[x] = num++;
}
vector<Edge> vec[MAXN];
inline void add_edge(int x, int y, int z) {
    vec[x].push_back((Edge){x, y, z});
    vec[y].push_back((Edge){y, x, z});
}
int low[MAXN], dfn[MAXN], times, fa[MAXN], cdis[MAXN], dis[MAXN], tot;
inline void Build(int x, int y, int w) {
    for(int i = y; i != x; i = fa[i]) cdis[i] = w, w += dis[i];
    cdis[++tot] = w; add_edge(tot, x, 0);//建方点 
    for(int i = y; i != x; i = fa[i]) add_edge(tot, i, min(cdis[i], w - cdis[i]));
}
void Tarjan(int x, int _fa) {
    dfn[x] = low[x] = ++times; fa[x] = _fa;
    for(int v, i = head[x]; i != -1; i = E[i].nxt) {
        if((v = E[i].v) == _fa) continue;
        if(!dfn[v]) dis[v] = E[i].w, Tarjan(v, x), low[x] = min(low[x], low[v]);
        else low[x] = min(low[x], dfn[v]);
        if(low[v] > dfn[x]) add_edge(x, v, E[i].w);
    }
    // can I take this into for ?
    for(int v, i = head[x]; i != -1; i = E[i].nxt) 
        if(fa[(v = E[i].v)] != x && dfn[v] > dfn[x])//如果不是负边，那么一定出现了环 
            Build(x, v, E[i].w);
}
int siz[MAXN], son[MAXN], top[MAXN], deep[MAXN], Index = 0, point[MAXN];
void dfs1(int x, int _fa) {
    fa[x] = _fa; siz[x] = 1; 
    for(int i = 0, v; i < vec[x].size(); i++) {
        if((v = vec[x][i].v) == _fa) continue;
        dis[v] = dis[x] + vec[x][i].w;
        deep[v] = deep[x] + 1;
        dfs1(v, x);
        siz[x] += siz[v];
        if(siz[v] > siz[son[x]]) son[x] = v;
    }
}
void dfs2(int x, int topf) {
    top[x] = topf; point[dfn[x] = ++Index] = x;
    if(!son[x]) return ;
    dfs2(son[x], topf); 
    for(int i = 0, v; i < vec[x].size(); i++) 
        if(!top[v = vec[x][i].v])
            dfs2(v, v);
}
int LCA(int x, int y) {
    while(top[x] != top[y]) {
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(deep[x] < deep[y]) swap(x, y);
    return y;
}
int Jump(int x, int lca) {
    int las;
    while(top[x] != top[lca]) las = top[x], x = fa[top[x]];//las = top[x] not x
    return x == lca ? las : point[dfn[lca] + 1];//这里要写lca 
}
int abs(int x) {
    return x < 0 ? -x : x;
}
int main() {
    #ifdef WIN32
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #endif
    tot = N = read(); M = read(); Q = read();
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z); AddEdge(y, x, z);
    }
    Tarjan(1, 0); dis[1] = 0; deep[1] = 1; 
    //for(int i = 1; i <= N; i++) printf("%d ", dfn[i]); puts("");
    //for(int i = 1; i <= N; i++) printf("%d ", vec[i].size()); puts("");
    //printf("%d\n", tot);
    dfs1(1, 0);
    dfs2(1, 1);
    //for(int i = 1; i <= tot; i++) printf("%d ", top[i]); puts("");
    while(Q--) {
        int x = read(), y = read();
        int lca = LCA(x, y);
        if(lca <= N) {printf("%d\n", dis[x] + dis[y] - (dis[lca] << 1)); continue;}
        int p1 = Jump(x, lca);
        int p2 = Jump(y, lca);
        int ans = dis[x] - dis[p1] + dis[y] - dis[p2] + min(abs(cdis[p2] - cdis[p1]),
                                                            cdis[lca] - abs(cdis[p2] - cdis[p1]));
        printf("%d\n", ans);
    }
    return 0;
}