思路：构建圆方树，然后如果两个点的lca是圆点，直接算，否则跳到环上相应的位置，再求环上两个点的最短距离。

代码1(在重链上跳)：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headstruct Circle_Square_Tree { const static int N = 2e4 + 10; vector
          
           
             > g[N]; int fa[N], dp[N], sz[N], son[N], top[N], dfn[N], to[N], cnt, n; LL dis[N], cir[N]; //环的大小 bool vis[N];//记录到方点的最短距离是否经过回边 inline void dfs1(int u, int o) { fa[u] = o; sz[u] = 1; dp[u] = dp[o] + 1; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; LL w = g[u][i].se; if(v != o) { dis[v] = dis[u] + w; dfs1(v, u); sz[u] += sz[v]; if(sz[v] > sz[son[u]]) son[u] = v; } } } inline void dfs2(int u, int t) { top[u] = t; dfn[u] = ++cnt; to[cnt] = u; if(!son[u]) return ; dfs2(son[u], t); for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; if(v != fa[u] && v != son[u]) dfs2(v, v); } } inline void init(int _n) { cnt = 0; n = _n; dp[0] = 0; dfs1(1, 0); dfs2(1, 1); } inline int lca(int u, int v) { int fu = top[u], fv = top[v]; while(fu != fv) { if(dp[fu] >= dp[fv]) u = fa[fu], fu = top[u]; else v = fa[fv], fv = top[v]; } if(dp[u] <= dp[v]) return u; else return v; } inline int jump(int u, int lca) { int res; while(top[u] != top[lca]) res = top[u], u = fa[top[u]]; if(u == lca) return res; else return to[dfn[lca]+1]; } inline LL query(int u, int v) { int l = lca(u, v); if(l <= n) return dis[u]+dis[v]-2*dis[l]; int uu = jump(u, l), vv = jump(v, l); LL d1 = dis[uu]-dis[l], d2 = dis[vv]-dis[l]; if(!vis[uu]) d1 = cir[l]-d1; if(!vis[vv]) d2 = cir[l]-d2; return dis[u]-dis[uu]+dis[v]-dis[vv]+min(abs(d1-d2), cir[l]-abs(d1-d2)); }}CST;const int N = 1e4 + 10;int n, m, q, u, v, w;vector
            
              g[N];int dfn[N], low[N], fa[N], cnt = 0, tot = 0;LL dep[N];int a[N];inline void solve(int u, int v, int d) { int cnt = 0; LL sum = d; for (int i = v; i != u; i = fa[i]) sum += dep[i] - dep[fa[i]], a[++cnt] = i; a[++cnt] = u; LL dis = 0; ++tot; for (int i = cnt; i >= 1; --i) { LL D = min(dis, sum-dis); if(D == dis) CST.vis[a[i]] = true; else CST.vis[a[i]] = false; CST.g[a[i]].pb({tot, D}); CST.g[tot].pb({a[i], D}); dis += dep[a[i-1]]-dep[a[i]]; } CST.cir[tot] = sum;}inline void tarjan(int u, int o) { fa[u] = o; dfn[u] = low[u] = ++cnt; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; int w = g[u][i].se; if(v == o) continue; if(!dfn[v]) { dep[v] = dep[u] + w; tarjan(v, u); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dfn[v]); if(low[v] > dfn[u]) { CST.g[u].pb({v, w}); CST.g[v].pb({u, w}); } } for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; int w = g[u][i].se; if(v == o) continue; if(fa[v] != u && dfn[v] > dfn[u]) { solve(u, v, w); } }}int main() { scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), g[u].pb({v, w}), g[v].pb({u, w}); tot = n; tarjan(1, 0); CST.init(n); while(q--) { scanf("%d %d", &u, &v); printf("%lld\n", CST.query(u, v)); } return 0;}
            
           
          
         
        
       
      
     
    

代码2（倍增跳）：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
    
     using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
     
      #define pli pair
      
       #define pii pair
       
        #define piii pair
        
         #define pdd pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headstruct Circle_Square_Tree { const static int N = 2e4 + 10; vector
          
           
             > G[N]; int dp[N], anc[N][18], n; LL dis[N], cir[N]; //环的大小 bool vis[N];//记录到方点的最短距离是否经过回边 vector
            
              g[N]; int dfn[N], low[N], fa[N], cnt, tot; int a[N]; inline void solve(int u, int v, int d) { int cnt = 0; LL sum = d; for (int i = v; i != u; i = fa[i]) sum += dis[i] - dis[fa[i]], a[++cnt] = i; a[++cnt] = u; LL DIS = 0; ++tot; for (int i = cnt; i >= 1; --i) { LL D = min(DIS, sum-DIS); if(D == DIS) vis[a[i]] = true; else vis[a[i]] = false; G[a[i]].pb({tot, D}); G[tot].pb({a[i], D}); DIS += dis[a[i-1]]-dis[a[i]]; } cir[tot] = sum; } inline void tarjan(int u, int o) { fa[u] = o; dfn[u] = low[u] = ++cnt; for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; int w = g[u][i].se; if(v == o) continue; if(!dfn[v]) { dis[v] = dis[u] + w; tarjan(v, u); low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dfn[v]); if(low[v] > dfn[u]) { G[u].pb({v, w}); G[v].pb({u, w}); } } for (int i = 0; i < g[u].size(); ++i) { int v = g[u][i].fi; int w = g[u][i].se; if(v == o) continue; if(fa[v] != u && dfn[v] > dfn[u]) { solve(u, v, w); } } } inline void dfs(int u, int o) { anc[u][0] = o; dp[u] = dp[o] + 1; for (int i = 1; i < 18; ++i) anc[u][i] = anc[anc[u][i-1]][i-1]; for (int i = 0; i < G[u].size(); ++i) { int v = G[u][i].fi; LL w = G[u][i].se; if(v == o) continue; dis[v] = dis[u] + w; dfs(v, u); } } inline void init(int _n) { tot = n = _n; cnt = 0; dis[0] = dp[1] = 0; tarjan(1, 0); dfs(1, 1); } inline int lca(int u, int v) { if(dp[u] < dp[v]) swap(u, v); for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] >= dp[v]) u = anc[u][i]; if(u == v) return u; for (int i = 17; i >= 0; --i) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; return anc[u][0]; } inline int jump(int u, int lca) { for (int i = 17; i >= 0; --i) if(dp[anc[u][i]] > dp[lca]) u = anc[u][i]; return u; } inline LL query(int u, int v) { int l = lca(u, v); if(l <= n) return dis[u]+dis[v]-2*dis[l]; int uu = jump(u, l), vv = jump(v, l); LL d1 = dis[uu]-dis[l], d2 = dis[vv]-dis[l]; if(!vis[uu]) d1 = cir[l]-d1; if(!vis[vv]) d2 = cir[l]-d2; return dis[u]-dis[uu]+dis[v]-dis[vv]+min(abs(d1-d2), cir[l]-abs(d1-d2)); }}CST;int n, m, q, u, v, w;int main() { scanf("%d %d %d", &n, &m, &q); for (int i = 1; i <= m; ++i) scanf("%d %d %d", &u, &v, &w), CST.g[u].pb({v, w}), CST.g[v].pb({u, w}); CST.init(n); while(q--) { scanf("%d %d", &u, &v); printf("%lld\n", CST.query(u, v)); } return 0;}