Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxNum = 100000;
- const int maxCost = 1 << 30;
- ll numCities, numImportant;
- bool important[maxNum];
- vector<pair<ll, ll> > graph[maxNum];
- pair<ll, ll> solve(ll current, ll previous){
- ll maxSum = 0, cost = 0, sum = 0;
- for (ll i = 0; i < graph[current].size(); i++){
- ll next = graph[current][i].first;
- ll distance = graph[current][i].second;
- if (next == previous){
- continue;
- }
- pair<ll, ll> curr = solve(next, current);
- maxSum = max(maxSum, min(distance, curr.first));
- sum += min(distance, curr.first);
- cost += curr.second;
- }
- if (important[current]){
- cost += sum;
- maxSum = maxCost;
- }
- else{
- cost += sum - maxSum;
- }
- return make_pair(maxSum, cost);
- }
- int main(){
- cin >> numCities >> numImportant;
- for (ll i = 1; i < numCities; i++){
- ll from_city, to_city, cost;
- cin >> from_city >> to_city >> cost;
- graph[from_city].push_back(make_pair(to_city, cost));
- graph[to_city].push_back(make_pair(from_city, cost));
- }
- memset(important, false, sizeof(important));
- for (ll i = 0; i < numImportant; i++){
- ll city;
- cin >> city;
- important[city] = true;
- }
- cout << solve(0, -1).second << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement