fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define BIT(i, x) (((x) >> (i)) & 1)
  4. #define task ""
  5. using namespace std;
  6. using ll = long long;
  7. using ld = long double;
  8.  
  9. const int N = 2e5 + 2;
  10. const ll Inf = 1e16;
  11. int n, m, k;
  12. int x[20];
  13. int dp[N];
  14. ll d[20][N];
  15. vector<pair<int, ll>> nadj[N];
  16. int bonker[20];
  17.  
  18. void Read()
  19. {
  20.     cin >> n >> k;
  21. 	m = n - 1;
  22.     for (int i = 1; i <= m; ++i)
  23.     {
  24.         int u, v;
  25.         ll w;
  26.         cin >> u >> v >> w;
  27.         nadj[u].push_back({v, w});
  28.         nadj[v].push_back({u, w});
  29.     }
  30.     for (int i = 1; i <= k; ++i)
  31.         cin >> bonker[i] >> x[i];
  32. }
  33.  
  34. bool Check(int v)
  35. {
  36.     memset(dp, 0, sizeof dp);
  37.     for (int i = 1; i <= n; ++i)
  38.     {
  39.         int cur = 0;
  40.         for (int j = 1; j <= k; ++j)
  41.             if (d[j][i] <= v)
  42.                 cur |= 1 << (j - 1);
  43.         ++dp[cur];
  44.     }
  45.     //cout << dp[1] << "\n";
  46.     for (int i = 1; i <= k; ++i)
  47.         for (int j = 1; j < (1 << k); ++j)
  48.             if (BIT(i - 1, j))
  49.                 dp[j] += dp[j ^ (1 << (i - 1))];
  50.     for (int j = 0; j < (1 << k); ++j)
  51.     {
  52.         ll cap = 0;
  53.         for (int i = 0; i < k; ++i)
  54.             if (BIT(i, j))
  55.                 cap += x[i + 1];
  56.         //cout << j << ": " << cap << " " << dp[j] << "\n";
  57.         if (cap < dp[j])
  58.             return false;
  59.     }
  60.     return true;
  61. }
  62.  
  63. bool Relax(int son, int par, ll w, ll d[N])
  64. {
  65.     if (d[son] > d[par] + w)
  66.     {
  67.         d[son] = d[par] + w;
  68.         return true;
  69.     }
  70.     return false;
  71. }
  72.  
  73. void Dijkstra(int x, ll d[N])
  74. {
  75.     fill_n(d, N, Inf);
  76.     d[x] = 0;
  77.     struct Tque
  78.     {
  79.         int v;
  80.         ll w;
  81.         Tque() {}
  82.         Tque(int v, ll w)
  83.         {
  84.             this->v = v;
  85.             this->w = w;
  86.         }
  87.         bool operator<(const Tque &a) const
  88.         {
  89.             return w > a.w;
  90.         }
  91.         bool Valid(ll d[])
  92.         {
  93.             return d[v] == w;
  94.         }
  95.     };
  96.     priority_queue<Tque> s;
  97.     s.push(Tque(x, 0));
  98.     while (s.size())
  99.     {
  100.         Tque c = s.top();
  101.         s.pop();
  102.         if (!c.Valid(d))
  103.             continue;
  104.         for (auto i : nadj[c.v])
  105.             if (Relax(i.first, c.v, i.second, d))
  106.                 s.push(Tque(i.first, d[i.first]));
  107.     }
  108. }
  109.  
  110. void Solve()
  111. {
  112.  
  113.     for (int i = 1; i <= k; ++i)
  114.         Dijkstra(bonker[i], d[i]);
  115.     ll l = 0, m, h = Inf;
  116.     while (l <= h)
  117.     {
  118.         m = (l + h) / 2;
  119.         if (Check(m))
  120.             h = m - 1;
  121.         else
  122.             l = m + 1;
  123.     }
  124.     cout << l;
  125. }
  126.  
  127. int32_t main()
  128. {
  129.     ios_base::sync_with_stdio(0);
  130.     cin.tie(0);
  131.     cout.tie(0);
  132.     if (fopen(task ".INP", "r"))
  133.     {
  134.         freopen(task ".INP", "r", stdin);
  135.         freopen(task ".OUT", "w", stdout);
  136.     }
  137.     Read();
  138.     Solve();
  139. }
Success #stdin #stdout 0.01s 18532KB
comments (?)
stdin
copy 
7 3
1 2 5
2 3 3
3 4 5
4 5 7
6 7 1
4 7 4
3 3
7 3
6 2
stdout
copy 
11
https://ideone.com/5AgLRf
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!