题意：仙人掌图最短路。
算法：圆方树DP，$O(n\log n+Q\log n)$
首先建出仙人掌圆方树（与点双圆方树的区别在于直接连割边，也就是存在圆圆边），然后考虑点u-v的最短路径，显然就是：在圆方树上u-v的路径上的所有边权之和，加上每个环（方点）中连出去的两个点的最短距离。
现在问题就是：如何求出环上两个点的最短路径。考虑这样设定边权，首先显然圆圆边的边权就是原图的边权，然后设一个环在搜索树中深度最小的点为这个环的根，则方圆边的边权是环的根到这个点的最短距离，这个可以在Tarjan的时候直接求出。
但是圆方树问题通常需要在LCA处分圆方点讨论。首先如果LCA是圆点，那么直接做即可。如果是方点，就需要决定要不要走环的另一侧，这个同样直接讨论即可。
具体见代码，感觉思路还是比较清晰的。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=;
int n,m,Q,u,v,w,tot,tim,top,dep[N],len[N],type[N],stk[N];
int dfn[N],low[N],dis[N],lst[N],fa[N][],sm[N][]; struct E{
int cnt,h[N],to[N<<],nxt[N<<],val[N<<];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
}G,G1; void work(int x,int k){
tot++; int t; len[tot]=dis[stk[top]]-dis[x]+lst[stk[top]];
do{
t=stk[top--];
int A=dis[t]-dis[x],B=len[tot]-A;
G1.add(tot,t,min(A,B)); type[t]=(A<=B);
}while (t!=k);
G1.add(x,tot,);
} void Tarjan(int x,int pre){
//printf("%d\n",x);
dfn[x]=low[x]=++tim; stk[++top]=x;
for (int i=G.h[x],k; i; i=G.nxt[i]){
if ((k=G.to[i])==pre) continue;
if (!dfn[k]){
dis[k]=dis[x]+G.val[i]; Tarjan(k,x);
//printf("%d %d %d %d\n",x,k,dfn[x],low[k]);
if (low[k]>dfn[x]) top--,G1.add(x,k,G.val[i]);
else if (low[k]==dfn[x]) work(x,k);
low[x]=min(low[x],low[k]);
}else low[x]=min(low[x],dfn[k]),lst[x]=G.val[i];
}
} void dfs(int x,int pre){
for (int i=G1.h[x],k; i; i=G1.nxt[i])
fa[k=G1.to[i]][]=x,dep[k]=dep[x]+,sm[k][]=G1.val[i],dfs(k,x);
} int lca(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
int t=dep[u]-dep[v],res=;
for (int i=; ~i; i--) if (t&(<<i)) res+=sm[u][i],u=fa[u][i];
if (u==v) return res;
for (int i=; ~i; i--) if (fa[u][i]!=fa[v][i])
res+=sm[u][i]+sm[v][i],u=fa[u][i],v=fa[v][i];
if (fa[u][]<=n) return sm[u][]+sm[v][]+res;
int A=sm[u][],B=sm[v][],mn;
if (type[u]==type[v]) mn=min(abs(A-B),len[fa[u][]]-abs(A-B));
else mn=min(A+B,len[fa[u][]]-A-B);
return res+mn;
} int main(){
freopen("bzoj2125.in","r",stdin);
freopen("bzoj2125.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q); tot=n;
rep(i,,m) scanf("%d%d%d",&u,&v,&w),G.add(u,v,w),G.add(v,u,w);
Tarjan(,); dfs(,);
//rep(i,1,tot) printf("%d ",low[i]); puts("");
rep(j,,) rep(i,,tot)
fa[i][j]=fa[fa[i][j-]][j-],sm[i][j]=sm[i][j-]+sm[fa[i][j-]][j-];
rep(i,,Q) scanf("%d%d",&u,&v),printf("%d\n",lca(u,v));
return ;
}