跳转至

仙人掌

例题

给定一个仙人掌，多组询问 \(u, v\) 之间最短路长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
const int MAXN= 2e5 + 3;
const int MAXM= 2e5 + 3;
const int MAXD=  18 + 3;
struct edge{int u, v, w;};
vector <edge> V1[MAXN];
vector <edge> V2[MAXN];
vector <int> H[MAXN];
int n, D[MAXN], W[MAXN], F[MAXD][MAXN];
int o, X[MAXN], L[MAXN];
bool E[MAXN];
void dfs1(int u, int f){
    D[u] = D[f] + 1, F[0][u] = f;
    for(auto &e : V1[u]) if(e.v != f){
        if(D[e.v] && D[e.v] < D[u]){
            int a = e.u;
            int b = e.v;
            int c = ++ o, t = c + n;
            H[c].push_back(a);
            L[c] = W[a] - W[b] + e.w;
            while(a != b)
                E[a] = true, a = F[0][a], H[c].push_back(a);
            for(auto &x : H[c]){
                int w = min(W[x] - W[b], L[c] - W[x] + W[b]);
                V2[x].push_back(edge{x, t, w});
                V2[t].push_back(edge{t, x, w});
            }
        } else if(!D[e.v]){
            W[e.v] = W[u] + e.w, dfs1(e.v, u);
        }
    }
    for(auto &e : V1[u]) if(D[e.v] > D[u]){
        if(!E[e.v]){
            V2[e.u].push_back({e.u, e.v, e.w});
            V2[e.v].push_back({e.v, e.u, e.w});
        }
    }
}
int d = 18;
void dfs2(int u, int f){
    D[u] = D[f] + 1, F[0][u] = f;
    up(1, d, i) F[i][u] = F[i - 1][F[i - 1][u]];
    for(auto &e : V2[u]) if(e.v != f){
        X[e.v] = X[e.u] + e.w;
        dfs2(e.v, u);
    }
}
int lca(int u, int v){
    if(D[u] < D[v]) swap(u, v);
    dn(d, 0, i) if(D[F[i][u]] >= D[v]) u = F[i][u];
    if(u == v) return u;
    dn(d, 0, i) if(F[i][u] != F[i][v]) u = F[i][u], v = F[i][v];
    return F[0][u];
}
int jump(int u, int v){
    dn(d, 0, i) if(D[F[i][v]] >  D[u]) v = F[i][v];
    return v;
}
int dis(int x, int y){
    int t = lca(x, y);
    if(t > n){
        int u = jump(t, x);
        int v = jump(t, y);
        int w = abs(W[u] - W[v]);
        int l = min(w, L[t - n] - w);
        return X[x] - X[u] + X[y] - X[v] + l;
    } else {
        return X[x] + X[y] - 2 * X[t];
    }
}
int m, q;
int qread();
int main(){
    n = qread(), m = qread(), q = qread();
    up(1, m, i){
        int u = qread(), v = qread(), w = qread();
        V1[u].push_back(edge{u, v, w});
        V1[v].push_back(edge{v, u, w});
    }
    dfs1(1, 0);
    dfs2(1, 0);
    up(1, q, i){
        int u = qread(), v = qread();
        printf("%d\n", dis(u, v));
    }
    return 0;
}