#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAX_N 40010
#define MAX_M 80010

struct node
{
       int t, next, len;
       node (int _t = 0, int _next = -1, int _len = 0)
       {
            t = _t, next = _next, len = _len;
       }
};

node tree[MAX_M];
int tf[MAX_N];

int ord[MAX_M], first[MAX_N], dep[MAX_M], dist[MAX_M];
int f[MAX_M][17], logn[MAX_M];// logn[i]: (int)log (2, i)
bool visited[MAX_N];
int num, root;

inline void add(int p, int a, int b, int c)
{
       tree[p] = node (b, tf[a], c);
       tf[a] = p;
}

void dfs(int v, int deep)
{
     visited[v] = true;
     ord[++num] = v, dep[num] = deep;
     if (!first[v]) first[v] = num;
     for (int i = tf[v]; i != -1; i = tree[i].next)
     {
         if (!visited[tree[i].t])
         {
            dist[tree[i].t] = dist[v] + tree[i].len;
            dfs (tree[i].t, deep + 1);
            ord[++num] = v, dep[num] = deep;   
         }
     }
}

void RMQ_LCA(void)
{
     logn[0] = -1;
     for (int i = 1; i <= num; i++)
         f[i][0] = i;
     for (int j = 1, s = 1; s <= num; s <<= 1, j++)
     {
         for (int i = 1; i + s<= num; i++)
         {
             if (dep[f[i][j - 1]] < dep[f[i + s][j - 1]])
                f[i][j] = f[i][j - 1];
             else f[i][j] = f[i + s][j - 1];
         }
     }
}

int LCA(int a, int b)
{
    a = first[a], b = first[b];
    if (a > b) swap (a, b);
    int k = logn[b - a + 1], s = 1 << k;
    if (dep[f[a][k]] < dep[f[b - s + 1][k]])
       return ord[f[a][k]];
    else return ord[f[b - s + 1][k]];
}

int n, m;
char ch[16];

int main(void)
{	scanf("%d%d", &n, &m);
	logn[0] = -1;
	for (int i = 1; i < MAX_M; i++)
	    logn[i] = (i & (i - 1)) ? logn[i - 1]: logn[i - 1] + 1;
    memset (tf, -1, sizeof (tf));
	for (int i = 1, a, b, c; i <= m * 2; i += 2)
    {   
        scanf ("%d%d%d%s", &a, &b, &c, ch);
        add (i, a, b, c);
        add (i + 1, b, a, c);
	}
	dfs (1, 0);
	RMQ_LCA();
	scanf ("%d", &n);
	for (int i = 1, a, b; i <= n; i++)
	{
        scanf ("%d%d", &a, &b);
        int lca = LCA (a, b);
        printf ("%d\n", dist[a] + dist[b] - 2 * dist[lca]);
    }
	return 0;
}

• Re:LCA ----> RMQ (2490) reimu 2011-12-02 19:38:35
  • 咦??点一下就发出去了?? (31) reimu 2011-12-02 19:40:31