题目链接 数据结构课上机碰到的题目，也太硬核了…… 题面上的特别条件m-n<21是关键，要怎么用呢？ 先随便选一个点作为根建一棵树，那么分以下两种情况来讨论：

• 若 s 到 t 的最短路径不经过非树边，直接求出 LCA 就可以轻松得出答案。
• 若 s 到 t 的最短路径经过非树边，就可以直接用非树边的端点作为 s 到 t 的中转点来更新答案。由于非树边最多有 21 条，这样的特殊点最多有 42 个，直接预处理出这 42 个点到其它点的最短路就可以了。

这里建树直接写了一个树剖，方便后面求 LCA。 稀疏图上 SPFA 快的一比……

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct Graph
{
	struct Vertex
	{
		vector<int> o, i;
		int siz, dep, top, dfn;
	};
	struct Edge : pair<int, int>
	{
		ll len;
		Edge(int x, int y, ll z) : pair<int, int>(x, y), len(z) {}
	};
	vector<Vertex> v;
	vector<Edge> e;
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		v[ed.first].o.push_back(e.size());
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
	int ch(int u, int i = 0)
	{
		return e[v[u].o[i]].second;
	}
	int fa(int u, int i = 0)
	{
		return e[v[u].i[i]].first;
	}
};
struct BellmanFord : Graph
{
	BellmanFord(int n) : Graph(n) {}
	void ask(int s, vector<ll> &d)
	{
		d.assign(v.size(), INF);
		vector<int> flag(v.size(), d[s] = 0);
		for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
			for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len;
					if (!flag[to])
						flag[to] = 1, q.push_back(to);
				}
	}
};
struct TreeDiagram : BellmanFord
{
	TreeDiagram(const Graph &g, int root) : BellmanFord(g.v.size())
	{
		build(root, g);
		int cnt = v[root].dfn = v[root].dep = 1;
		dfs(v[root].top = root, cnt);
	}
	void build(int u, const Graph &g)
	{
		v[u].siz = 1;
		for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
			if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz)
			{
				build(to, g);
				v[u].siz += v[to].siz;
				Graph::add(g.e[k]);
				if (v[ch(u)].siz < v[to].siz)
					swap(v[u].o.front(), v[u].o.back());
			}
	}
	void dfs(int u, int &cnt)
	{
		for (int i = 0, to; i < v[u].o.size(); ++i)
		{
			v[to = ch(u, i)].dfn = ++cnt;
			v[to].top = i ? to : v[u].top;
			v[to].dep = v[u].dep + 1;
			dfs(to, cnt);
		}
	}
	int lca(int x, int y)
	{
		for (; v[x].top != v[y].top; x = fa(v[x].top))
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
		if (v[x].dep < v[y].dep)
			swap(x, y);
		return y;
	}
};
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	BellmanFord g(n + 1);
	for (int i = 0, x, y, z; i < m; ++i)
	{
		scanf("%d%d%d", &x, &y, &z);
		g.add({x, y, z});
		g.add({y, x, z});
	}
	TreeDiagram t(g, 1);
	vector<ll> d[63];
	for (int i = m = 0; i < n; ++i)
		if (t.v[i].o.size() + t.v[i].i.size() < g.v[i].o.size())
			g.ask(i, d[m++]);
	t.ask(1, d[m]);
	scanf("%d", &n);
	for (int i = 0, x, y; i < n; ++i)
	{
		scanf("%d%d", &x, &y);
		ll ans = d[m][x] + d[m][y] - 2 * d[m][t.lca(x, y)];
		for (int j = 0; j < m; ++j)
			ans = min(ans, d[j][x] + d[j][y]);
		printf("%lld\n", ans);
	}
}