How far away ？

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 10412 Accepted Submission(s): 3777

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<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 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(0<k<=40000).The houses are labeled from 1 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

3 2

1 2 10

3 1 15

1 2

2 3

2 2

1 2 100

1 2

2 1

Sample Output

100

模板题.离线算法:dfs+并查集.

/*

    2586    31MS    10288K    1637 B    G++

*/

#include"cstdio"

#include"cstring"

#include"vector"

using namespace std;

const int MAXN=;

typedef pair<int,int> P;

vector<P> G[MAXN];

vector<P> que[MAXN];

int par[MAXN];

int fnd(int x)

{

    if(par[x]==x)

        return x;

    par[x]=fnd(par[x]);

}

int vis[MAXN];

int d[MAXN];

int ans[MAXN];

void dfs(int u,int fa)

{

    par[u]=u;

    for(int i=;i<que[u].size();i++)

    {

        P no=que[u][i];

        if(vis[no.first])    ans[no.second]=d[u]+d[no.first]-*d[fnd(no.first)];

    }

    vis[u]=;

    for(int i=;i<G[u].size();i++)

    {

        P now=G[u][i];

        if(now.first==fa)    continue;

        d[now.first]=d[u]+now.second;

        dfs(now.first,u);

        par[now.first]=u;

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        memset(vis,,sizeof(vis));

        memset(d,,sizeof(d));

        memset(ans,,sizeof(ans));

        int V,Q;

        scanf("%d%d",&V,&Q);

        for(int i=;i<=V;i++)

        {

            G[i].clear();

            que[i].clear();

        }

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

        {

            int u,v,cost;

            scanf("%d%d%d",&u,&v,&cost);

            G[u].push_back(P(v,cost));

            G[v].push_back(P(u,cost));

        }

        for(int i=;i<=Q;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            que[u].push_back(P(v,i));

            que[v].push_back(P(u,i));

        }

        dfs(,-);

        for(int i=;i<=Q;i++)

        {

            printf("%d\n",ans[i]);

        }

    //    printf("\n");

    }

    return ;

}

因为查询较少,朴素的求LCA算法就能过。

/*

        Accepted    2586    62MS    7148K    1444B    G++

*/

#include"cstdio"

#include"cstring"

#include"vector"

using namespace std;

const int MAXN=;

typedef pair<int,int> P;

vector<P> G[MAXN];

int depth[MAXN];

int parent[MAXN];

void dfs(int u,int fa,int d)

{

    depth[u]=d;

    parent[u]=fa;

    for(int i=;i<G[u].size();i++)

    {

        P now=G[u][i];

        if(now.first!=fa)    dfs(now.first,u,d+);

    }

}

void Swap(int &a,int &b)

{

    int t=a;

    a=b;

    b=t;

}

int LCA(int u,int v)

{

    int d=;

    if(depth[u]<depth[v])    Swap(u,v);

    while(depth[u]>depth[v])

    {

        int fa=parent[u];

        for(int i=;i<G[fa].size();i++)

        {

            P now=G[fa][i];

            if(now.first==u)

            {

                d+=now.second;

                break;

            }

        }

        u=fa;

    }

    while(u!=v)

    {

        int fa=parent[u];

        for(int i=;i<G[fa].size();i++)

        {

            P now=G[fa][i];

            if(now.first==u)

            {

                d+=now.second;

                break;

            }

        }

        u=fa;

        fa=parent[v];

        for(int i=;i<G[fa].size();i++)

        {

            P now=G[fa][i];

            if(now.first==v)

            {

                d+=now.second;

                break;

            }

        }

        v=fa;

    }

    return d;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int V,Q;

        scanf("%d%d",&V,&Q);

        for(int i=;i<=V;i++)    G[i].clear();

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

        {

            int u,v,cost;

            scanf("%d%d%d",&u,&v,&cost);

            G[u].push_back(P(v,cost));

            G[v].push_back(P(u,cost));

        }

        dfs(,-,);

        while(Q--)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            printf("%d\n",LCA(u,v));

        }

    }

    return ;

}

巴特西

HDU2586(LCA应用:在带权树中求任意两点之间的距离)

How far away ？

最新文章

热门文章