HDU-2017"百度之星"程序设计大赛-初赛(B)-1002-Factory

ACM模版

描述

题解

其实，这个题的题解我是秒出的，当然，之所以没有写是因为这个秒出的题解也是被我秒掉了，我认识他会超时……始终是这样认为的……可是大概数据没有那么刁钻的极限情况，所以直接 LCA+暴力 就能过。

我们只需要暴力枚举两个子公司的办公室的任意组合，求最短距离即可，这部分就是 LCA 的过程，没有什么难度，所以堪称是模版题……然而想要一遍 AC 的我想了许久也没有敢写它，始终认为他会超时，所以就放弃了这个尝试的机会……不然这个题是可以一遍水过去的。

比赛中，最可怕的就是模版题你搞炸了……然而这次的题，两道题都是模版题，并且还都炸了，02 和 05，这个游戏真是不能玩……根本不能同台竞技~~~

代码

#include <cstdio>
#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
const int MAGIC = 20;

struct edge
{
    int x, w;
    edge(int x, int w) : x(x), w(w) {}
};

vector<edge> ve[MAXN];
vector<int> vi[MAXN];

int n, m;
int dep[MAXN];
int hed[MAXN];
int pre[MAXN][MAGIC];

void dfs(int x, int p)
{
    hed[x] = hed[p] + 1;
    pre[x][0] = p;
    for (int i = 1; i < MAGIC; ++i)
    {
        pre[x][i] = pre[pre[x][i - 1]][i - 1];
    }
    int y;
    for (int i = 0; i < ve[x].size(); ++i)
    {
        y = ve[x][i].x;
        if (y == p)
        {
            continue;
        }
        dep[y] = dep[x] + ve[x][i].w;
        dfs(y, x);
    }
}

int lca(int x, int y)
{
    if (hed[x] < hed[y])
    {
        swap(x, y);
    }
    int d = hed[x] - hed[y];
    for (int i = 0; i < MAGIC; ++i)
    {
        if ((d >> i) & 1)
        {
            x = pre[x][i];
        }
    }
    if (x == y)
    {
        return x;
    }
    for (int i = MAGIC - 1; i >= 0; --i)
    {
        if (pre[x][i] != pre[y][i])
        {
            x = pre[x][i];
            y = pre[y][i];
        }
    }

    return pre[x][0];
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

int main()
{
    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(n), scan_d(m);
        for (int i = 1; i <= n; ++i)
        {
            ve[i].clear();
        }
        for (int i = 1; i <= m; ++i)
        {
            vi[i].clear();
        }
        int u, v, w;
        for (int i = 1; i < n; ++i)
        {
            scan_d(u), scan_d(v), scan_d(w);
            ve[u].push_back(edge(v, w));
            ve[v].push_back(edge(u, w));
        }
        int G, x;
        for (int i = 1; i <= m; ++i)
        {
            scan_d(G);
            for (int j = 0; j < G; ++j)
            {
                scan_d(x);
                vi[i].push_back(x);
            }
        }

        dfs(1, 0);

        int Q, ans;
        scan_d(Q);
        while (Q--)
        {
            scanf("%d%d", &u, &v);
            ans = INF;
            for (auto x : vi[u])
            {
                for (auto y : vi[v])
                {
                    ans = min(ans, dep[x] + dep[y] - 2 * dep[lca(x, y)]);
                }
            }

            printf("%d\n", ans);
        }
    }

    return 0;
}