Skip to content

14019: 【原4019】撤退

题目

题目描述

author: Naïve Yan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4019 

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

Limits

对于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。

yyong119's solution

#include <cstdio>
#include <vector>
#include <queue>
#define MAX_N 20005
using namespace std;
int n, a, b, c;
vector<int> adj[MAX_N], dist[MAX_N];
int dist_from_a[MAX_N], dist_from_b[MAX_N], dist_from_c[MAX_N];

void find_dist(int p, int dist_from_p[]) {

    queue<int> que;
    while (!que.empty()) que.pop();
    que.push(p);
    while(!que.empty()) {
        int cur = que.front(); que.pop();
        for (int i = 0; i < adj[cur].size(); ++i) {
            int next = adj[cur][i];
            if (!dist_from_p[next]) {
                dist_from_p[next] = dist_from_p[cur] + dist[cur][i];
                que.push(next);
            }
        }
    }
}

int main() {

    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i < n; ++i) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        adj[u].push_back(v); dist[u].push_back(c);
        adj[v].push_back(u); dist[v].push_back(c);
    }
    find_dist(a, dist_from_a);
    find_dist(b, dist_from_b);
    find_dist(c, dist_from_c);
    dist_from_a[a] = 0;
    dist_from_b[b] = 0;
    dist_from_c[c] = 0;
    // for (int i = 1; i <= n; ++i) {
    //     printf("%d %d %d\n", dist_from_a[i], dist_from_b[i], dist_from_c[i]);
    // }
    int p, min_dist = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) {
        int total_dist = dist_from_a[i] + dist_from_b[i] + dist_from_c[i];
        if (total_dist < min_dist) {
            min_dist = total_dist;
            p = i;
        }
    }
    printf("%d\n%d\n", p, min_dist);
    return 0;
}