# 14119: 【原4119】撤退

### 题目描述

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

## Sample Input

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

## Sample Output

``````4
16
``````

## 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;
ed[cnt] = v;
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;
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;
}
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;

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

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