> #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;
> }
> 

• 咦??点一下就发出去了?? (31) reimu 2011-12-02 19:40:31