【题目大意】多组询问仙人掌上两个点的最短路

【题解】缩点，破环，仙人掌变成树，求LCA。

# include <stdio.h>
# include <vector>
# include <map> 
# include <string.h>
using namespace std;

int n, m;
inline int abs(int x) {return x>0?x:-x;} 

int head[300010], next[300010], to[300010], tot=0; 
int scc=0, dfn[300010], low[300010], DFN=0; 
vector<int> s[300010], son[300010]; 
int st[300010], stn=0; 
int fa[500010][16], dep[500010], size[500010];
map<int,int> d[300010], f[300010]; 
int D[300010]; 
inline void add(int u, int v, int tw) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	if(f[u].find(v)==f[u].end()) 
		f[u][v]=tw;
	else f[u][v]=min(f[u][v], tw); 
}
inline int getdep(int x) {
	if(fa[x][0]==0) dep[x]=1;
	if(dep[x]) return dep[x]; 
	return dep[x]=getdep(fa[x][0])+1;
}
	 
inline void init() {
	memset(dep, 0, sizeof(dep)); 
	for (int i=1; i<=15; ++i) {
		for (int j=1; j<=scc; ++j) fa[j][i] = fa[fa[j][i-1]][i-1];
		for (int j=n+1; j<=n*2; ++j) fa[j][i] = fa[fa[j][i-1]][i-1];
	}
	for (int i=1; i<=scc; ++i) getdep(i);
	for (int i=n+1; i<=n*2; ++i) getdep(i);
} 
int tx, ty;
inline int lca(int x,int y)   {  
	if(dep[x]<dep[y]) swap(x,y); 
    for(int j=15; j>=0; --j)  
    	if(dep[fa[x][j]]>=dep[y]) x=fa[x][j]; 
    if(x==y) return x;
	for (int j=15; j>=0; --j) 
		if(fa[x][j] != fa[y][j]) x=fa[x][j], y=fa[y][j];
	tx=x,ty=y;
	return fa[x][0];
}
inline void tarjan(int x) {
	low[x]=dfn[x]=++DFN;
	st[++stn]=x;
	for (int i=head[x]; i; i=next[i]) {
		if(dfn[to[i]] != 0) {
			low[x] = min(low[x], dfn[to[i]]);
		} else {
			tarjan(to[i]);
			if(low[to[i]] == dfn[x]) {
				++scc;
				son[x].push_back(scc); 
				s[scc].push_back(x); 
				fa[scc][0]=n+x; 
				int t;
				do {
					t=st[stn--];
					s[scc].push_back(t); 
					fa[n+t][0]=scc; 
				} while(t != to[i]); 
			}
			low[x] = min(low[x], low[to[i]]);
		}
	}
}
inline void pre(int x) {
 	stn=0;
 	for (int i=0,sz=s[x].size(); i<sz; ++i) st[++stn]=s[x][i];
	st[++stn]=s[x][0];
	for (int i=1; i<stn; ++i) {
		size[x] += f[st[i]][st[i+1]];
		if(i!=stn-1) d[x][st[i+1]]=d[x][st[i]]+f[st[i]][st[i+1]]; 
	}
	int s1=2, t=stn-1;
	while(s1<=t) {
		if(D[st[s1-1]]+f[st[s1-1]][st[s1]]<D[st[t+1]]+f[st[t+1]][st[t]]) { 
			D[st[s1]]=D[st[s1-1]]+f[st[s1-1]][st[s1]];
			++s1;
		} else {
		 	D[st[t]]=D[st[t+1]]+f[st[t+1]][st[t]]; 
		 	--t;
		}
	}
	for (int i=1,sz=s[x].size(); i<sz; ++i)	for (int j=0, szt=son[s[x][i]].size(); j<szt; ++j) pre(son[s[x][i]][j]);
}
		 
int main() {
	scanf("%d%d", &n, &m);	int T;scanf("%d", &T); 
	for (int i=1, u, v, tw; i<=m; ++i) {
		 scanf("%d%d%d", &u, &v, &tw);
		 add(u, v, tw);
		 add(v, u, tw); 
	}
	tarjan(1); init(); 
	for (int j=0,sz=son[1].size();j<sz; ++j) pre(son[1][j]);

	while(T--) {
		int x, y;
		scanf("%d%d", &x, &y);
		int LCA=lca(n+x,n+y);
		if(LCA>n) printf("%d\n", D[x]+D[y]-2*D[LCA-n]); 
		else {
			int ans = D[x]+D[y]-D[tx-n]-D[ty-n];
			int tmp = abs(d[LCA][tx-n]-d[LCA][ty-n]);
			ans+=min(tmp, size[LCA]-tmp);
			printf("%d\n", ans);
		}
	}
	return 0;
}