How far away ？

Time Limit: / MS (Java/Others)    Memory Limit: / K (Java/Others)

Total Submission(s):     Accepted Submission(s): 

Problem Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=), indicating the number of test cases.

  For each test case,in the first line there are two numbers n(<=n<=) and m (<=m<=),the number of houses and the number of queries. The following n- lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(<k<=).The houses are labeled from  to n.

  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

Sample Output

#include <iostream>

#include <cstdio>

#include <cstring>

#define scan(x) scanf("%d",&x)

#define scan2(x,y) scanf("%d%d",&x,&y)

#define scan3(x,y,z) scanf("%d%d%d",&x,&y,&z)

using namespace std;

const int Max=;

const int E=*;

int head[Max],nex[E],pnt[E],cost[E],edge;

int vex[Max<<],R[Max<<],vis[Max],dis[Max],first[Max],tot;

//!!vex R 长度要Max*2,因为算法特性会生成顶点数两倍的序列

int n;

void Addedge(int u,int v,int c)

{

    pnt[edge]=v;cost[edge]=c;

    nex[edge]=head[u];head[u]=edge++;

}

void dfs(int u,int deep)

{

    vis[u]=;

    vex[++tot]=u;   //以tot为编号的的节点

    first[u]=tot;   //u节点的编号为tot

    R[tot]=deep;    //tot编号节点的深度

    for(int x=head[u];x!=-;x=nex[x])

    {

        int v=pnt[x],c=cost[x];

        if(!vis[v])

        {

            dis[v]=dis[u]+c;

            dfs(v,deep+);

            vex[++tot]=u;

            R[tot]=deep;

        }

    }

}

int dp[Max<<][];

//!!dp长度要Max*2,,因为算法特性会生成顶点数两倍的序列

void ST(int n) //n是2*n-1

{

    int x,y;

    for(int i=;i<=n;i++) dp[i][]=i;

    for(int j=;(<<j)<=n;j++)

    {

        for(int i=;i+(<<j)-<=n;i++)

        {

          x=dp[i][j-];y=dp[i+(<<(j-))][j-];

          dp[i][j]=(R[x]<R[y]?x:y);

        }

    }

}

int RMQ(int l,int r)

{

    int k=,x,y;

    while((<<(k+))<=r-l+) k++;

    x=dp[l][k];y=dp[r-(<<k)+][k];

    return (R[x]<R[y])?x:y;

}

int LCA(int u,int v)

{

    int x=first[u],y=first[v];

    if(x>y) swap(x,y);

    int res=RMQ(x,y);  //在u,v之间的最小深度节点即为lca

    return vex[res];

}

void Init()

{

    edge=;

    memset(head,-,sizeof(head));

    memset(nex,-,sizeof(nex));

    memset(vis,,sizeof(vis));

}

int main()

{

    int T,Q;

    for(scan(T);T;T--)

    {

        Init();

        int u,v,c;

        scan2(n,Q);

        for(int i=;i<n-;i++)

        {

            scan3(u,v,c);

            Addedge(u,v,c);

            Addedge(v,u,c);

        }

        tot=;dis[]=;

        dfs(,);

        ST(*n);

        while(Q--)

        {

            scan2(u,v);

            int lca=LCA(u,v);

            printf("%d\n",dis[u]+dis[v]-*dis[lca]);

        }

    }

    return ;

}