记录编号	47131	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2012-10-30 22:02:24	内存使用	3.83 MiB

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 20000 + 10, INF = 0x7ffffff;
int n, f[3][N];
vector<int> G[N], e[N];
void Bellman(int s, int o) {
    bool l[N] = {0};
    queue<int> q;
    fill(f[o], f[o]+n+1, INF);
    f[o][s] = 0, l[s] = 1, q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop(); l[u] = 0;
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i];
            if(f[o][v] > f[o][u] + e[u][i]) {
                f[o][v] = f[o][u] + e[u][i];
                if(!l[v]) l[v] = 1, q.push(v);
            }
        }
    }
}
int main() {
    freopen("escapeb.in", "r", stdin);
    freopen("escapeb.out", "w", stdout);
    int a, b, c, u, v, w;
    scanf("%d %d %d %d", &n, &a, &b, &c);
    for(int i=1; i<n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back(v); e[u].push_back(w);
        G[v].push_back(u); e[v].push_back(w);
    }
    Bellman(a, 0);
    Bellman(b, 1);
    Bellman(c, 2);
    int s = INF, t, j = 1;
    for(int i=n; i>0; i--) {
        //fprintf(stderr, "%d: %d %d %d\n", i, f[0][i], f[1][i], f[2][i]);
        if((t = f[0][i] + f[1][i] + f[2][i]) < s)
            s = t, j = i;
    }
    printf("%d\n%d\n", j, s);
    return 0;
}