Advertisement
Guest User

fdasfsa

a guest
Jan 19th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const int maxNum = 100000;
  7. const int maxCost = 1 << 30;
  8.  
  9. ll numCities, numImportant;
  10. bool important[maxNum];
  11. vector<pair<ll, ll> > graph[maxNum];
  12.  
  13. pair<ll, ll> solve(ll current, ll previous){
  14.     ll maxSum = 0, cost = 0, sum = 0;
  15.     for (ll i = 0; i < graph[current].size(); i++){
  16.         ll  next = graph[current][i].first;
  17.         ll distance = graph[current][i].second;
  18.  
  19.         if (next == previous){
  20.             continue;
  21.         }
  22.  
  23.         pair<ll, ll> curr = solve(next, current);
  24.         maxSum = max(maxSum, min(distance, curr.first));
  25.         sum += min(distance, curr.first);
  26.         cost += curr.second;
  27.     }
  28.  
  29.     if (important[current]){
  30.         cost += sum;
  31.         maxSum = maxCost;
  32.     }
  33.  
  34.     else{
  35.         cost += sum - maxSum;
  36.     }
  37.  
  38.     return make_pair(maxSum, cost);
  39. }
  40.  
  41. int main(){
  42.     cin >> numCities >> numImportant;
  43.     for (ll i = 1; i < numCities; i++){
  44.         ll from_city, to_city, cost;
  45.         cin >> from_city >> to_city >> cost;
  46.  
  47.         graph[from_city].push_back(make_pair(to_city, cost));
  48.         graph[to_city].push_back(make_pair(from_city, cost));
  49.     }
  50.  
  51.     memset(important, false, sizeof(important));
  52.     for (ll i = 0; i < numImportant; i++){
  53.         ll city;
  54.         cin >> city;
  55.         important[city] = true;
  56.     }
  57.  
  58.     cout << solve(0, -1).second << endl;
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement