Description：

给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

$1\le N,Q\le10^5$ ，时限 $0.1s$

Solution：

边仙人掌上的最短路，可以借鉴树上求最短路的方法求出 $LCA$ 再减深度。

既然是仙人掌，那就不存在环套环的情况。

用圆方树的思想，先用 $tarjan$ 把所有环找出来，然后删掉环上的所有边，再把所有点都连到环内深度最小的点。这样就把仙人掌化成了一颗树，然后把环上除了最高点之外的所有点打上这个环的标记。

然后需要处理出在原图 $dfs$ 序上各个点到根的距离 $dis$ ，在原图上各个点到根的距离 $d$ ，以及新图上每个点的深度。

每次询问再新图上求 $LCA$ ，

如果 $x$ 和 $y$ 的 $LCA$ 是 $y$ ，返回 $d[x]-d[y]$ 。

如果 $x$ 和 $y$ 的 $LCA$ 再环上，设 $a$ 为 $x$ 找到的环上的点， $b$ 为 $y$ 找到的环上的点，环长为 $len$ ，则答案为： $d[x]-d[a]+d[y]-d[b]+min(|dis[a]-dis[y]|,len-|dis[a]-dis[y]|)$

如果 $LCA$ 在树上，则答案为 $d[x]+d[y]-2\times d[LCA]$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 10010

#define MAXQ 10010

#define MAXM (MAXN * 10)

struct edge

{

	int to,nxt,w;

}e[MAXM << 1];

bool block[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[edgenum].to = b;e[edgenum].w = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	return;

}

void init()

{

	scanf("%d%d%d",&n,&m,&q);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

		add(b,a,c);

	}

	return;

}

bool v[MAXN];

int deep[MAXN],d[MAXN];

int f[MAXN][15];

void SPFA()

{

	memset(v,0,sizeof(v));

	memset(d,0x3f,sizeof(d));

	d[0] = 0;

	queue<int> q;

	q.push(1);

	d[1] = 0;

	v[1] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].w)

			{

				d[e[i].to] = d[k] + e[i].w;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return;

}

int dis[MAXN],dfn[MAXN],tot = 0;

int cnt = 0;

int ins[MAXN],len[MAXN];

int pre[MAXN];

void tarjan(int k)

{

	dfn[k] = ++tot;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if((i > m * 2 - 1) || (i == (pre[k] ^ 1)))continue;

		if(dfn[e[i].to] == 0)

		{

			dis[e[i].to] = dis[k] + e[i].w;

			pre[e[i].to] = i;

			tarjan(e[i].to);

		}

		else if(dfn[e[i].to] < dfn[k])

		{

			++cnt;

			len[cnt] = e[i].w;

			for(int p = k;p != e[i].to;p = e[pre[p] ^ 1].to)

			{

				block[pre[p]] = block[pre[p] ^ 1] = true;

				add(e[i].to,p,0);

				ins[p] = cnt;

				len[cnt] += e[pre[p]].w;

			}

		}

	}

	return;

}

void dfs(int k)

{

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(!block[i] && deep[e[i].to] == 0)

		{

			f[e[i].to][0] = k;

			deep[e[i].to] = deep[k] + 1;

			dfs(e[i].to);

		}

	}

	return;

}

void LCA_pre()

{

	for(int i = 1;i <= 14;++i)

		for(int k = 1;k <= n;++k)

			f[k][i] = f[f[k][i - 1]][i - 1];

	return;

}

int query(int x,int y)

{

	int a,b;

	if(deep[x] < deep[y])swap(x,y);

	a = x,b = y;

	for(int i = 14;i >= 0;--i)

		if(deep[f[x][i]] >= deep[y])

			x = f[x][i];

	if(x == y)return d[a] - d[x];

	for(int i = 14;i >= 0;--i)

		if(f[x][i] != f[y][i])

			x = f[x][i],y = f[y][i];

	if(ins[x] != 0 && ins[x] == ins[y])

	{

		int r = abs(dis[x] - dis[y]);

		return d[a] - d[x] + d[b] - d[y] + min(r,len[ins[x]] - r);

	}

	return d[a] - d[f[x][0]] + d[b] - d[f[y][0]];

}

void work()

{

	int x,y;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&x,&y);

		printf("%d\n",query(x,y));

	}

	return;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	init();

	SPFA();

	tarjan(1);

	deep[1] = 1;

	dfs(1);

	LCA_pre();

	work();

	return 0;

}