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

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;
}