Uva12862 - Intrepid climber

題目大意

你在一座山頂，其他朋友還在山腰，你要去向他們告知你已經攻頂了，雖然往下爬不會累，但往上爬會累，你要找出一條最不會累的路徑
(你在整個樹的頂點，每個 path 會有 weight，朋友在子樹的某個節點中，往上爬才消耗能量)

重點觀念

• dfs?

分析

• 你會發現如果把任意結果再加上最後去的節點到山頂消耗的能量，得出來的數字都會一樣，所以只要算出這個樹再減掉離頂點要消耗最多能量的能量就好了

程式題目碼

#include <iostream>
#include <vector>
using namespace std;

bool friends[100005];
vector<pair<int, int> > g[100005];
int max_depth, consumed_energy;

int dfs(int cur, int depth) {
    int num_friends = 0;
    if (friends[cur]) {
        max_depth = max(max_depth, depth);
        num_friends += 1;
    }
    for (auto i = g[cur].begin(); i != g[cur].end(); i++) {
        int next_friends = dfs(i->first, depth + i->second);
        if (next_friends > 0) {
            consumed_energy += i->second;
            num_friends += next_friends;
        }
    }

    return num_friends;
}

int main() {
    int n, f;
    while (cin >> n >> f) {
        for (int i = 1; i < n + 1; i++) {
            friends[i] = false;
            g[i].clear();
        }
        for (int i = 0; i < n - 1; i++) {
            int root, child, weight;
            cin >> root >> child >> weight;
            g[root].push_back(make_pair(child, weight));
        }
        for (int i = 0; i < f; i++) {
            int where_friend;
            cin >> where_friend;
            friends[where_friend] = true;
        }
        max_depth = 0, consumed_energy = 0;
        dfs(1, 0);

        cout << consumed_energy - max_depth << endl;
    }

    return 0;
}