Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2019
372
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.17 KB | None | 0 0
  1. #ifdef DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long double ld;
  10.  
  11. #ifdef DEBUG
  12. #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  13. #else
  14. #define eprintf(...) ;
  15. #endif
  16.  
  17. #define sz(x) ((int) (x).size())
  18. #define TASK "text"
  19.  
  20. const int inf = (int) 1.01e9;
  21. const long long infll = (long long) 1.01e18;
  22. const ld eps = 1e-9;
  23. const ld pi = acos((ld) -1);
  24.  
  25. #ifdef DEBUG
  26. mt19937 mrand(300);
  27. #else
  28. mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
  29. #endif
  30.  
  31. int rnd(int x) {
  32.   return mrand() % x;
  33. }
  34.  
  35. void precalc() {
  36. }
  37.  
  38. #define ws wwwwwws
  39.  
  40. const int maxn = 2005, maxm = 105;
  41. int c[3];
  42. int n[2];
  43. vector<int> g[2][maxn];
  44. int ws[2][maxn];
  45.  
  46. bool read() {
  47.   if (scanf("%d%d%d", &c[0], &c[1], &c[2]) < 3) {
  48.     return false;
  49.   }
  50.   for (int t = 0; t < 2; t++) {
  51.     scanf("%d", &n[t]);
  52.     ws[t][0] = -1;
  53.     for (int v = 0; v < n[t]; v++) {
  54.       g[t][v].clear();
  55.       int k;
  56.       scanf("%d", &k);
  57.       g[t][v].resize(k);
  58.       for (int i = 0; i < k; i++) {
  59.         int u, w;
  60.         scanf("%d%d", &u, &w);
  61.         u--;
  62.         g[t][v][i] = u;
  63.         ws[t][u] = w;
  64.       }
  65.     }
  66.   }
  67.   return true;
  68. }
  69.  
  70. vector<int> path;
  71. vector<int> ps;
  72.  
  73. void getPath(int t, int v) {
  74.   for (int i = 0; i < sz(g[t][v]); i++) {
  75.     int u = g[t][v][i];
  76.     int l = sz(path);
  77.     path.push_back(u);
  78.     ps.push_back(-1);
  79.     getPath(t, u);
  80.     int r = sz(path);
  81.     path.push_back(u);
  82.     ps.push_back(-1);
  83.     ps[l] = r;
  84.     ps[r] = l;
  85.   }
  86. }
  87.  
  88. long long dp[maxn][maxm][maxm];
  89. long long dpe[maxn][maxm][maxm];
  90.  
  91. long long cost(int w0, int w1) {
  92.   return (long long) c[2] * abs(w1 - w0) - (long long) c[1] * w0 - (long long) c[0] * w1;
  93. }
  94.  
  95. void dfs(int v) {
  96.   for (int i = 0; i < sz(path); i++) {
  97.     for (int j = i; j <= sz(path); j++) {
  98.       dp[v][i][j] = 0;
  99.     }
  100.   }
  101.   for (int it = 0; it < sz(g[1][v]); it++) {
  102.     int u = g[1][v][it];
  103.     dfs(u);
  104.     for (int i = sz(path) - 1; i >= 0; i--) {
  105.       for (int j = sz(path); j >= i; j--) {
  106.         auto &cur = dp[v][i][j];
  107.         for (int k = i; k < j; k++) {
  108.           cur = min(cur, dp[v][i][k] + dpe[u][k][j]);
  109.         }
  110.       }
  111.     }
  112.   }
  113.   if (!v) {
  114.     return;
  115.   }
  116.   for (int i = 0; i < sz(path); i++) {
  117.     for (int j = i; j <= sz(path); j++) {
  118.       auto &cur = dpe[v][i][j];
  119.       cur = dp[v][i][j];
  120.       for (int l = i; l < j; l++) {
  121.         int r = ps[l];
  122.         if (r < l || r >= j) {
  123.           continue;
  124.         }
  125.         cur = min(cur, dp[v][l + 1][r] + cost(ws[0][path[l]], ws[1][v]));
  126.       }
  127.     }
  128.   }
  129. }
  130.  
  131. void solve() {
  132.   path.clear();
  133.   ps.clear();
  134.   getPath(0, 0);
  135.   dfs(0);
  136.   long long res = dp[0][0][sz(path)];
  137.   for (int v = 1; v < n[0]; v++) {
  138.     res += (long long) c[1] * ws[0][v];
  139.   }
  140.   for (int v = 1; v < n[1]; v++) {
  141.     res += (long long) c[0] * ws[1][v];
  142.   }
  143.   printf("%lld\n", res);
  144. }
  145.  
  146. int main() {
  147.   precalc();
  148. #ifdef DEBUG
  149.   assert(freopen(TASK ".in", "r", stdin));
  150.   assert(freopen(TASK ".out", "w", stdout));
  151. #endif
  152.   while (read()) {
  153.     solve();
  154. #ifdef DEBUG
  155.     eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
  156. #endif
  157.   }
  158.   return 0;
  159. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement