本文共 3953 字，大约阅读时间需要 13 分钟。

$$迷宫花坛\left(\mathrm{g}\mathrm{a}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{n}\right)$$

题目链接：

题目

圣玛格丽特学园的一角有一个巨大、如迷宫般的花坛。大约有一个人这么高的大型花坛，做成迷宫的形状，深受中世纪贵族的喜爱。维多利加的小屋就坐落在这迷宫花坛的深处。某一天早晨，久城同学要穿过这巨大的迷宫花坛，去探望感冒的维多利加。

整个迷宫可以用 $N$ 个路口与 $M$ 条连接两个不同路口的无向通道来描述。路口被标号为 $1$ 到 $N$ ，每条通道有各自的长度。整个迷宫一定是连通的，迷宫中可能存在若干个环路，但是，出于美观考虑，每个路口最多只会属于一个简单环路。例如，图 $1$ 所示的迷宫是非常美观的，但图 $2$ 则不符合我们的描述，因为 $3$ 号路口同属于两个简单环。

输入

第一行 $2$ 个整数 $N,M$ ，表示迷宫花坛的路口数和通道数；

接下来 $N$ 行，每行 $3$ 个整数 $x,y,z$ ，描述一条连接路口 $x$ 与路口 $y$ ，长度为 $z$ 的通道；

再接下来 $1$ 行包含一个整数 $Q$ ，表示询问数量；

之后 $Q$ 行，每行 $2$ 个整数 $x,y$ ，描述一个询问。

输出

对于每个询问输出一行一个整数，表示最短距离。

样例输入

4 41 2 12 3 21 3 23 4 122 41 3

样例输出

32

数据范围

对于 $30\%$ 的数据， $N\le 100$ ；

另有 $30\%$ 的数据，保证 $N=M$ ；

对于 $100\%$ 的数据， $1\le N\le 100,000，Q\le 200,000，1\le x,y\le N，1\le z\le 1000.$

思路

这道题就是一道裸的，我刚写了模板，就直接看那个模板的博客，注释也不写了。

（这里要开快读快输，因为数据大了一点，当然变量的大小也要开大一些）

代码

#include
   
    #include
    
     #include
     
      #define ll long longusing namespace std;struct node {   	ll x, to, nxt;}e[400001], ee[400001];ll n, m, q, x, y, z, w, ans;ll nn, KK, KKK, lca, X, Y;ll l[100001], fa[200001], dep[200001], dis[200001], diss[200001];ll dfn[200001], low[200001], le[200001], lee[200010], fath[21][200001];ll read() {   	ll an = 0, zhengfu = 1;	char c = getchar();	while (c < '0' || c > '9') {   		if (c == '-') zhengfu = -zhengfu;		c = getchar();	}	while (c >= '0' && c <= '9') {   		an = an * 10 + c - '0';		c = getchar();	}	return an * zhengfu;}void add0(ll x, ll y, ll z) {   	e[++KK] = (node){   z, y, le[x]}; le[x] = KK;	e[++KK] = (node){   z, x, le[y]}; le[y] = KK;}void add(ll x, ll y, ll z) {   	ee[++KKK] = (node){   z, y, lee[x]}; lee[x] = KKK;	ee[++KKK] = (node){   z, x, lee[y]}; lee[y] = KKK;}void build(ll x, ll y, ll lon) {   	nn++;	ll len = lon;	for (ll i = y; i != fa[x]; i = fa[i]) {   		diss[i] = len;		len += l[i];	}	diss[nn] = diss[x];	diss[x] = 0;	for (ll i = y; i != fa[x]; i = fa[i]) {   		len = min(diss[i], diss[nn] - diss[i]);		add(i, nn, len);	}}void dfs1(ll now) {   	dfn[now] = low[now] = ++w;	for (ll i = le[now]; i; i = e[i].nxt)		if (e[i].to != fa[now]) {   			if (!dfn[e[i].to]) {   				fa[e[i].to] = now;				l[e[i].to] = e[i].x;				dfs1(e[i].to);				low[now] = min(low[now], low[e[i].to]);			}			else low[now] = min(low[now], dfn[e[i].to]);			if (low[e[i].to] > dfn[now]) add(now, e[i].to, e[i].x);		}		for (ll i = le[now]; i; i = e[i].nxt)		if (fa[e[i].to] != now && dfn[now] < dfn[e[i].to])			build(now, e[i].to, e[i].x);}void dfs2(ll now) {   	dep[now] = dep[fath[0][now]] + 1;	for (int i = 1; i <= 20; i++)		fath[i][now] = fath[i - 1][fath[i - 1][now]];	for (ll i = lee[now]; i; i = ee[i].nxt)		if (ee[i].to != fath[0][now]) {   			fath[0][ee[i].to] = now;			if (!dis[ee[i].to]) dis[ee[i].to] = dis[now] + ee[i].x;				else dis[ee[i].to] = min(dis[ee[i].to], dis[now] + ee[i].x);			dfs2(ee[i].to);		}}ll LCA(ll x, ll y) {   	if (dep[x] < dep[y]) swap(x, y);	for (ll i = 20; i >= 0; i--)		if (dep[fath[i][x]] >= dep[y])			x = fath[i][x];	for (ll i = 20; i >= 0; i--)		if (fath[i][x] != fath[i][y]) {   			x = fath[i][x];			y = fath[i][y];		}		X = x;	Y = y;	if (x == y) return x;	return fath[0][x];}void writec(ll x) {   	if (x > 9) writec(x / 10);	putchar(x % 10 + '0');}void write(ll x) {   	if (x < 0) writec(-x);	writec(x);	putchar('\n');}int main() {   	n = read();	m = read();	nn = n;	for (ll i = 1; i <= m; i++) {   		x = read();		y = read();		z = read();		add0(x, y, z);	}		dfs1(1);	fath[0][1] = 1;	dfs2(1);		q = read();	for (ll i = 1; i <= q; i++) {   		x = read();		y = read();		lca = LCA(x, y);		if (lca > n) {   			ans = dis[x] - dis[X] + dis[y] - dis[Y];			ll far = abs(diss[X] - diss[Y]);			ans = ans + min(far, diss[lca] - far);		}		else ans = dis[x] - dis[lca] + dis[y] - dis[lca];		write(ans);	}		return 0;}