Skip to content

14119: 【原4119】撤退

题目

题目描述

author: Ca. 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4119

Description

在一个外星人的遗迹中分布着三样道具,当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。 遗迹可以看作是由N个房间(编号1..N)和N-1条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。 现在,我们的队员已经在编号为A,B,C的房间内拿到道具,并且准备撤退。由于只有一架直升机,所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上,才能够使三人到达该房间的距离之和最短。

Input Format

第1行:四个整数N A B C; 第2..N行:每行三个整数u,v,w,表示存在连接房间u,v的通道,长度为w。

Output Format

第1行:一个整数,表示汇合房间的编号。若存在多个解,输出字典序最小的一个; 第2行:一个整数,表示三人到该房间的距离之和。

Sample Input

5 3 1 4
3 5 5
4 3 9
4 1 7
1 2 1

Sample Output

4
16

Data Range

对于50%的数据:1 <= N <= 1,000; 对于100%的数据:1 <= N <= 20,000; 1 <= A,B,C,u,v <= N,且A,B,C不相等,u,v不相等; 1 <= w <= 1,000。

FineArtz's solution

/* 撤退 */
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 20000;

int n, A, B, C;
int head[MAXN + 5] = {0}, ed[MAXN + 5] = {0}, nxt[MAXN + 5] = {0}, len[MAXN + 5] = {0};
int cnt = 0;
int h[MAXN + 5] = {0}, e[MAXN + 5] = {0}, nn[MAXN + 5] = {0}, l[MAXN + 5] = {0};
int m = 0;
int dist[MAXN + 5] = {0}, depth[MAXN + 5] = {0}, fa[MAXN + 5][20] = {0};

inline void addEdge(int u, int v, int w){
    ++cnt;
    nxt[cnt] = head[u];
    ed[cnt] = v;
    head[u] = cnt;
    len[cnt] = w;
}

inline void addedge(int u, int v, int w){
    ++m;
    nn[m] = h[u];
    e[m] = v;
    h[u] = m;
    l[m] = w;
}

void calcDist(int x){
    int q[MAXN + 5];
    bool b[MAXN + 5]= {0};
    int front = 0, rear = 0;
    q[rear++] = x;
    dist[x] = 0;
    depth[x] = 1;
    b[x] = true;
    while (front != rear){
        int now = q[front];
        ++front;
        for (int i = head[now]; i != 0; i = nxt[i]){
            int next = ed[i];
            if (!b[next]){
                b[next] = true;
                addedge(now, next, len[i]);
                fa[next][0] = now;
                depth[next] = depth[now] + 1;
                dist[next] = dist[now] + len[i];
                q[rear++] = next;
            }
        }
    }
}

inline int lca(int p, int q){
    if (depth[p] > depth[q]){
        int t = p;
        p = q;
        q = t;
    }
    int def = depth[q]  - depth[p];
    for (int i = 0; (1 << i) <= def; ++i){
        if ((1 << i) & def)
            q = fa[q][i];
    }
    if (p != q){
        for (int i = (int)log2(n); i >= 0; --i){
            if (fa[p][i] != fa[q][i]){
                p = fa[p][i];
                q = fa[q][i];
            }
        }
        p = fa[p][0];
    }
    return p;
}

inline int dis(int p, int q){
    int x = lca(p, q);
    return dist[p] + dist[q] - 2 * dist[x];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> A >> B >> C;
    for (int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    calcDist(1);
    for (int j = 1; (1 << j) <= n; ++j){
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    int ans = 2147483647, ansi = 0;
    for (int i = 1; i <= n; ++i){
        int d = dis(i, A) + dis(i, B) + dis(i, C);
        if (ans > d){
            ans = d;
            ansi = i;
        }
    }
    cout << ansi << '\n' << ans << '\n';
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cmath"
#include "cstring"
using namespace std;

class edge {
public:
    int to = 0;
    int length = 0;
    edge* next = nullptr;
};

class tree_node {
public:
    int parent = 0;
    int depth = 0;
    int dist = 0;
    int parent_list[16] = { 0 };
    edge* head = nullptr, * rear = nullptr;
};

tree_node tree_data[20009];
int root_pos = 0;

void dfs(int pos) {
    if (pos == root_pos) {
        tree_data[pos].depth = 0;
    }
    else {
        tree_data[pos].depth = tree_data[tree_data[pos].parent].depth + 1;
        int k = (int)(log(tree_data[pos].depth) / log(2));
        tree_data[pos].parent_list[0] = tree_data[pos].parent;
        for (int i = 1; i <= k; ++i) {
            tree_data[pos].parent_list[i] = tree_data[tree_data[pos].parent_list[i - 1]].parent_list[i - 1];
        }
    }
    for (auto p = tree_data[pos].head->next; p; p = p->next) {
        if (p->to != tree_data[pos].parent) {
            tree_data[p->to].parent = pos;
            tree_data[p->to].dist = tree_data[pos].dist + p->length;
            dfs(p->to);
        }
    }
}

int LCA(int pos1, int pos2) {
    while (tree_data[pos1].depth < tree_data[pos2].depth) {
        int k = int(log(tree_data[pos2].depth - tree_data[pos1].depth) / log(2));
        pos2 = tree_data[pos2].parent_list[k];
    }
    while (tree_data[pos2].depth < tree_data[pos1].depth) {
        int k = int(log(tree_data[pos1].depth - tree_data[pos2].depth) / log(2));
        pos1 = tree_data[pos1].parent_list[k];
    }
    while (pos1 != pos2) {
        int k = int(log(tree_data[pos1].depth) / log(2));
        for (int i = k; i >= 0; --i) {
            if (i == 0 || tree_data[pos1].parent_list[i] != tree_data[pos2].parent_list[i]) {
                pos1 = tree_data[pos1].parent_list[i];
                pos2 = tree_data[pos2].parent_list[i];
            }
        }
    }
    return pos1;
}

int cal_distance(int pos1, int pos2) {
    int lca = LCA(pos1, pos2);
    return tree_data[pos1].dist + tree_data[pos2].dist - 2 * tree_data[lca].dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, a, b, c;
    cin >> n >> a >> b >> c;

    for (int i = 1; i <= n; ++i) {
        tree_data[i].rear = tree_data[i].head = new edge;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        tree_data[u].rear->next = new edge;
        tree_data[u].rear = tree_data[u].rear->next;
        tree_data[u].rear->to = v;
        tree_data[u].rear->length = w;

        tree_data[v].rear->next = new edge;
        tree_data[v].rear = tree_data[v].rear->next;
        tree_data[v].rear->to = u;
        tree_data[v].rear->length = w;
    }

    root_pos = a;
    dfs(a);

    int ans_pos = LCA(b, c), ans_val = tree_data[b].dist + tree_data[c].dist - tree_data[ans_pos].dist;

    cout << ans_pos << "\n" << ans_val;

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 2e4 + 100;

struct edgeNode {
    int data;
    int weight;
    edgeNode *next;

    edgeNode(int d = 0, int w = 0, edgeNode *n = 0)
        : data(d), weight(w), next(n) {}
};

struct verNode {
    int data;
    edgeNode *head;

    verNode(int d = 0, edgeNode *h = 0) : data(d), head(h) {}
};

struct Node {
    int data;
    int sum;

    Node(int d = 0, int s = 0) : data(d), sum(s) {}
};

int N, A, B, C, sum = 1e9, pos = 0;
int Distance[4][maxN] = {0};
verNode *nodes[maxN];
bool isVisited[maxN] = {0};
Node que[100000];

void BFS(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> A >> B >> C;

    for (int i = 1; i <= N; i++) {
        nodes[i] = new verNode(i);
    }

    for (int i = 0; i < N - 1; i++) {
        int temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        nodes[temp1]->head = new edgeNode(temp2, temp3, nodes[temp1]->head);
        nodes[temp2]->head = new edgeNode(temp1, temp3, nodes[temp2]->head);
    }

    BFS(A);
    BFS(B);
    BFS(C);

    for (int i = N; i >= 1; i--) {
        int temp = Distance[0][i] + Distance[1][i] + Distance[2][i];
        if (temp <= sum) {
            sum = temp;
            pos = i;
        }
    }

    cout << pos << '\n' << sum;

    return 0;
}

void BFS(int s) {
    for (int i = 0; i <= N; i++) {
        isVisited[i] = 0;
    }

    int head = 0, tail = 0;
    isVisited[s] = 1;
    que[tail++] = Node(s, 0);

    while (head != tail) {
        Node temp = que[head++];
        edgeNode *p = nodes[temp.data]->head;

        while (p != 0) {
            if (isVisited[p->data]) {
                p = p->next;
                continue;
            } else {
                isVisited[p->data] = 1;
                que[tail++] = Node(p->data, temp.sum + p->weight);
                if (s == A) {
                    Distance[0][p->data] = temp.sum + p->weight;
                } else if (s == B) {
                    Distance[1][p->data] = temp.sum + p->weight;
                } else {
                    Distance[2][p->data] = temp.sum + p->weight;
                }
                p = p->next;
            }
        }
    }
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define MAX_N 20010
#define INF 0xfffffff
using namespace std;

int distA[MAX_N], distB[MAX_N], distC[MAX_N];
int n, a, b, c, ans = INF, pos = 0;
vector<int> point[MAX_N], length[MAX_N];

void solve(int origin, int dist[]) {

    for (int i = 1; i <= n; ++i) dist[i] = INF;
    dist[origin] = 0;

    bool flag[n]; memset(flag, false, sizeof(flag));
    queue<int> q; while(!q.empty()) q.pop();

    q.push(origin); flag[origin] = true;
    while (!q.empty()) {
        int now = q.front(); 
        q.pop(); flag[now] = false;
        for (int i = 0; i < point[now].size(); ++i) {
            int next = point[now][i];
            if (dist[next] > dist[now] + length[now][i]) {
                dist[next] = dist[now] + length[now][i];
                if (flag[next] == false) {
                    q.push(next);
                    flag[next] = true;
                }
            }
        }
    }
}

int main() {

    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i < n; ++i) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        point[u].push_back(v); length[u].push_back(w);
        point[v].push_back(u); length[v].push_back(w);
    }
    solve(a, distA);
    solve(b, distB);
    solve(c, distC);
    for (int i = n; i > 0; --i)
        if (distA[i] + distB[i] + distC[i] <= ans) {
            ans = distA[i] + distB[i] + distC[i];
            pos = i;
        }
    // for (int i = 1; i <= n; ++i) printf("%d ", distA[i]); printf("\n");
    // for (int i = 1; i <= n; ++i) printf("%d ", distB[i]); printf("\n");
    // for (int i = 1; i <= n; ++i) printf("%d ", distC[i]); printf("\n");
    printf("%d\n%d\n", pos, ans);
    return 0;
}