CSUST选拔赛题解之-Problem F: 挑战迷宫

Problem F: 挑战迷宫

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 135 Solved: 34
[ Submit][ Status][ Web Board]

Description

小翔和小明正在挑战一个神奇的迷宫。迷宫由n个房间组成，每个房间的编号为1~n，其中1号房间是他们俩初始位置，
所有房间一共由n-1条路连接，使得房间两两之间能够相互达到（构成一棵树），每条路的长度为Wi。
每当小翔和小明都在房间时，他们的神奇手机就能显示两人的位置（两人分别在哪两个房间），现在想请聪明的ACMer
快速地算出他们之间的最短距离。

Input

第一行输入整数n（0<n<=100000），表示迷宫有n个房间。
接下来n-1行，每行输入3个整数u,v,w（1<=u,v<=n,u!=v,w<=10000），表示编号为u和v的房间之间有一条长为w的路。
第n+1行输入整数m（0<m<=100000），表示有m次询问。
接来下m行，每行输入2个整数u,v（1<=u,v<=n），表示小翔和小明当前所在房间的编号。

Output

对于每次询问的输出占一行，输出一个整数d表示小翔和小明之间的最短距离。

Sample Input

Sample Output

HINT

解题思路：这是一道LCA的模板题，我也是在补题的时候刚学的LCA（最近公共祖先），这里我用的是tarjan离线（还有在线的算法，还没怎么学）算法求的（后面详细说一下这个算法），这个算法的作用就是从某个根节点出发，算出每个节点到这个根节点的距离dist[i]，然后两个节点间的最短距离就为 dist[x] + dist[y] - 2*dist[z]，z为x和y的LCA。做题前提是你要会邻接表，不会的话可以点进去看看哈。

邻接表的实现

AC代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<time.h>
#include<map>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
#include<iomanip>
#define N 100005

using namespace std;

int head[N], root[N], vis[N], dist[N], m, cnt, cnt2, head2[N];
  //dist[i]为节点i到根节点的距离
int x[N], y[N], z[N];
 //z[i]为x[i]和y[i]的LCA
struct Edge
{
    int End;
    int Len;
    int next;
}e[2*N],e2[2*N];

void Add_Edge(int u, int v, int w)
{
    e[cnt].End = u;
    e[cnt].Len = w;
    e[cnt].next = head[v];
    head[v] = cnt ++;
}

void Add_question(int u, int v, int i)
{
    e2[cnt2].End = u;
    e2[cnt2].Len = i;
    e2[cnt2].next = head2[v];
    head2[v] = cnt2 ++;
}

int Find_root(int k)
{
    if(root[k] == k)
        return root[k] = k;
    return root[k] = Find_root(root[k]);
}

void tarjan(int k)
{
    vis[k] = 1;
    root[k] = k;
    for(int i = head2[k]; i != -1 ; i = e2[i].next) {  //查找LCA
        if(vis[e2[i].End])
            z[e2[i].Len] = Find_root(e2[i].End);
    }
    for(int i = head[k]; i != -1; i = e[i].next) {
        if(!vis[e[i].End]) {
            dist[e[i].End] = dist[k] + e[i].Len;
            tarjan(e[i].End);
            root[e[i].End] = k;
        }
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        int u, v, w;
        cnt = 0;
        cnt2 = 0;
        memset(head, -1, sizeof(head));
        memset(head2, -1, sizeof(head2));
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n - 1; i ++) {
            scanf("%d%d%d", &u, &v, &w);
            Add_Edge(u, v, w);
            Add_Edge(v, u, w);
        }
        scanf("%d", &m);
        for(int i = 0; i < m; i ++) { //储存要解决的问题
            scanf("%d%d", &u, &v);
            Add_question(u, v, i);
            Add_question(v, u, i);
            x[i] = u;
            y[i] = v;
            z[i] = 0;
        }
        dist[1] = 0;
        tarjan(1);
        for(int i = 0; i < m; i ++){ //离线解决
            printf("%d\n", dist[x[i]] + dist[y[i]] - 2 * dist[z[i]]);
        }

    }
    return 0;
}

秒客网