题目链接：http://poj.org/problem?id=1986
题意： 有 n 条边 m 个点 k 个询问，问你这对询问中的lca的最小代价是什么
题解： LCA模板题。
代码：
#include <cstdio> #include <vector> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int size = 4e5+5; struct edges { int to, w; int next; } ed[size], quer[size]; int head[size], fath[size], qhead[size], vis[size], dis[size]; int n, m, cnt=0, qcnt = 0; int find(int x) { if(fath[x] == x) return fath[x]; else return fath[x] = find(fath[x]); } void add(int u, int v, int w) { ed[cnt].to = v; ed[cnt].w = w; ed[cnt].next = head[u]; head[u] = cnt++; } void addQuer(int x, int y) { quer[qcnt].to = y; quer[qcnt].next = qhead[x]; qhead[x] = qcnt; qcnt ++; } void init() { cnt = qcnt = 0; memset(ed, 0, sizeof(ed)); memset(quer, 0, sizeof(quer)); memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); memset(qhead, -1, sizeof(qhead)); memset(dis, 0, sizeof(dis)); memset(fath, 0, sizeof(fath)); // for ( int i = 0; i <= n; i ++ ) fath[i] = i; } void Tarjan(int u) { fath[u] = u; vis[u] = 1; for ( int ind = head[u]; ind != -1; ind = ed[ind].next) { int to = ed[ind].to; if(!vis[to]) { dis[to] = dis[u]+ed[ind].w; Tarjan(to); fath[to] = u; } } for ( int i = qhead[u]; i != -1; i = quer[i].next) { int to = quer[i].to; if(vis[to]) { quer[i].w = dis[u]+dis[to]-2*dis[find(to)]; quer[i^1].w = quer[i].w; } } } int main() { #ifdef ONLINEJUDGE freopen("1986.in","r",stdin); #endif while( scanf("%d %d", &n, &m) != EOF ){ init(); for ( int i = 0; i < m; i ++ ) { int x, y, w; char ch; scanf("%d %d %d %c", &x, &y, &w, &ch); add(x, y, w); add(y, x, w); } int c; scanf("%d",&c); for ( int i = 0; i < c; i ++ ) { int a, b; scanf("%d %d", &a, &b); addQuer(a, b); addQuer(b, a); } Tarjan(1); for ( int i = 0; i < qcnt; i += 2 ) { printf("%d\n", quer[i].w); } } return 0; }