POJ1986

思路是裸的倍增LCA T飞了 已加常数优化

草刚才题号打错了

#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstring>
#include <cmath>
#include <list>
using namespace std;
list<pair<int, int> > edges[40010];
int t, n, logn, m, k, fa[30][40010], dist[40010], deep[40010];
void buildTree(int x, int dis) {
	dist[x] = dis;
	for(list<pair<int, int> >::iterator iter = edges[x].begin(); iter != edges[x].end(); iter++) {
		if(fa[0][x] == iter->first)    continue;
		fa[0][iter->first] = x;
		deep[iter->first] = deep[x] + 1;
		buildTree(iter->first, dis + iter->second);
	}
}
void buildST() {
	for(int i = 1; i <= logn; i++)
		for(int j = 1; j <= n; j++)
			fa[i][j] = fa[i - 1][fa[i - 1][j]];
}
int LCA(int x, int y) {
	if(deep[x] < deep[y]) swap(x, y);
	for(int i = logn; i >= 0; i--)
		if(deep[fa[i][x]] >= deep[y])
			x = fa[i][x];
	if(x == y)    return x;
	for(int i = logn; i >= 0; i--)
		if(fa[i][x] != fa[i][y])
			x = fa[i][x], y = fa[i][y];
	return fa[0][x];
}
inline int read() {
	int s = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while(isdigit(ch))  s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return s * f;
}
inline void ignore() {
	while(getchar() == ' ');
	while(isalpha(getchar()));
}
char trash_char;
int main() {
	n = read(), m = read();
	logn = log((double)n) / log(2.0);
	for(int i = 1; i <= m; i++) {
		int u = read(), v = read(), w = read();
		ignore();
		edges[u].push_back(make_pair(v, w));
		edges[v].push_back(make_pair(u, w));
	}
	buildTree(1, 0);
	buildST();
	k = read();
	while(k--) {
		int x = read(), y = read();
		printf("%d\n", dist[x] + dist[y] - (dist[LCA(x, y)] << 1));
	}
	system("pause");
	return 0;
}