思路是 构建圆方树 + 倍增 $LCA + tarjan$ 求解仙人掌上的最短路

调了一天了，求助。

禁止无意义回复。

#include<bits/stdc++.h>

#define N 20010
#define M 20010
#define ll long long

using namespace std;
int n, m, q, tot, fa[N], dfn[N], low[N], v[N], dep[N], cnt;
int stac[N], stot;
struct node {
	int to, val, next;
} e[M << 1];
map<int, ll> mp[N];
map<int, bool> vis[N];
int edge_id, head[N];
void add_edge(int u, int v, int val) {
	++edge_id;
	e[edge_id].next = head[u];
	e[edge_id].to = v;
	e[edge_id].val = val;
	head[u] = edge_id;
}

int jpfa[22][N];
ll jpval[22][N];
void tarjan(int x) {
	dfn[x] = low[x] = ++cnt, stac[++stot] = x;
	for(int i = head[x]; i; i = e[i].next) {
		if(e[i].to == fa[x]) continue;
		if(!dfn[e[i].to]) fa[e[i].to] = x, v[e[i].to] = e[i].val, tarjan(e[i].to);
		low[x] = min(low[x], low[e[i].to]);
		if(low[e[i].to] != dfn[x] || vis[x][e[i].to]) continue;
		ll ssum = v[x], tsum = 0;
		int gtot = stot;
		for(int i = head[x]; i; i = e[i].next) if(e[i].to == stac[stot]) ssum = e[i].val;
		++tot, fa[tot] = jpfa[0][tot] = x;
		while(gtot) {
			ssum += v[stac[gtot]];
			if(stac[gtot] == e[i].to) {
				--gtot;
				break;
			}
			--gtot;
		}
		int sstot = stot;
		for(stot = gtot + 1; stot <= sstot; stot++) {
			tsum += v[stac[stot]];
			mp[tot - n][stac[stot]] = tsum;
			jpfa[0][stac[stot]] = fa[stac[stot]] = tot, jpval[0][stac[stot]] = min(ssum - tsum, tsum);
			vis[x][stac[stot]] = 1;
		}
		stot = gtot;
	}
	if(low[x] == dfn[x]) jpfa[0][x] = fa[x], jpval[0][x] = v[x], --stot;
}

int dfs(int x) {
	if(dep[x]) return dep[x];
	return dep[x] = dfs(fa[x]) + 1; 
}

void build() {
	for(int i = 1; i <= 18; i++) 
		for(int j = 1; j <= tot; j++) 
			jpfa[i][j] = jpfa[i - 1][jpfa[i - 1][j]], 
			jpval[i][j] = jpval[i - 1][j] + jpval[i - 1][jpfa[i - 1][j]];
}

int A, B, LCA;
ll Ans;
void query(int x, int y) {
	Ans = 0;
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 18; i >= 0; i--) if(dep[x] - dep[y] >= (1 << i)) Ans += jpval[i][x], x = jpfa[i][x];
	for(int i = 18; i >= 0; i--) 
		if(jpfa[i][x] != jpfa[i][y]) 
			Ans += jpval[i][x] + jpval[i][y], x = jpfa[i][x], y = jpfa[i][y];
	A = x, B = y;
	if(x != y) LCA = jpfa[0][x];
	else LCA = x, A = B = 0;//, Ans -= jpval[0][A] + jpval[0][B];
}

int main() {
	scanf("%d%d%d", &n, &m, &q), tot = n;
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add_edge(u, v, w), add_edge(v, u, w);
	}
	dep[1] = 1, tarjan(1);
	for(int i = 2; i <= tot; i++) dfs(i);
	build();
	while(q--) {
		int u, v;
		scanf("%d%d", &u, &v);
		query(u, v);
		if(LCA <= n) printf("%lld\n", Ans + jpval[0][A] + jpval[0][B]);
		else printf("%lld\n", Ans + abs(mp[LCA - n][A] - mp[LCA - n][B]));
	}
	return 0;
}