The Shortest Statement

题目描述

给你一个有 $n$ 个点， $m$ 条边的无向连通图。有 $q$ 次询问，第 $i$ 次询问回答从 $u_i$ 到 $d_i$ 的最短路的长度。

$1 \le n, m \le 10^5, m - n \le 20$

题目大意

注意到 $m - n \le 20$ ，那就把它转成树来做，而多出来的边标记两端为特殊点，用特殊点跑 dij 即可。

代码

const int N = 1e5 + 50;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	struct Graph {
		int head[N], tot;
		struct Edge {
			int to, nxt, w;
		} e[N << 1];
		void Add (int u, int v, int w) {
			e[++tot] = (Edge) {v, head[u], w}, head[u] = tot;
		}

		vector <ll> dis[N];
		bool vis[N];
		priority_queue < pair <ll, int> > q;
		void Dij (int s) {
			memset (vis, 0, sizeof vis);
			vector<ll> &d = dis[s];
			d.resize(n + 1);
			for(int i = 1; i <= n; i++)
				d[i] = 1ll << 50;
			d[s] = 0;
			q.push(make_pair(0, s));
			while (!q.empty()) {
				pair <ll, int> x = q.top(); q.pop();
				int u = x.second;
				if (vis[u]) continue; vis[u] = 1;
				for (int i = head[u]; i; i = e[i].nxt) {
					int v = e[i].to;
					if(d[u] + e[i].w < d[v]) {
						d[v] = d[u] + e[i].w;
						q.push(make_pair(-d[v], v));
					}
				}
			}
		}
	} G;
	struct Tree{
		int head[N], tot;
		struct Edge {
			int to, nxt, w;
		} e[N << 1];
		void Add (int u, int v, int w) {
			e[++tot] = (Edge) {v, head[u], w}, head[u] = tot;
		}
		ll dis[N];
		int f[N][30], dep[N];
		void dfs(int u, int fa) {
			f[u][0] = fa; dep[u] = dep[fa] + 1;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to; if (v == fa) continue;
				dis[v] = dis[u] + e[i].w;
				dfs (v, u);
			}
		}
		void init() {
			dfs (1, 0);
			for (int j = 1; j <= 20; j++)
				for (int i = 1; i <= n; i++)
					f[i][j] = f[f[i][j-1]][j - 1];
		}
		int LCA(int u, int v) {
			if(dep[u] < dep[v]) swap(u, v);
			int h = dep[u] - dep[v];
			for(int i = 20; ~i; i--) if(h & (1 << i)) u = f[u][i];
			if(u == v) return u; 
			for(int i = 20; ~i; i--) if(f[u][i] ^ f[v][i]) u = f[u][i], v = f[v][i];
			return f[u][0];
		}
		ll Dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[LCA(u, v)];  }
	} T;
	vector <int> key;
	bool inKey[N];
	int fa[N];
	int find (int k) { return k == fa[k]? k: fa[k] = find(fa[k]); }
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int u = Read(), v = Read(), w = Read();
			G.Add(u, v, w); G.Add(v, u, w);
			int x = find (u), y = find(v);
			if (x == y) {
				if (!inKey[u]) key.emplace_back(u), inKey[u] = 1;
				if (!inKey[v]) key.emplace_back(v), inKey[v] = 1;
			} else {
				fa[x] = y;
				T.Add(u, v, w), T.Add(v, u, w);
			}
		}
		T.init();
		for (int u: key) G.Dij(u);
		for (int q = Read(); q--; ) {
			int u = Read(), v = Read();
			ll ans = T.Dis(u, v);
			for (int i: key) ans = min(ans, G.dis[i][u] + G.dis[i][v]);
			printf ("%lld\n", ans);
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}