Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef DEBUG
- #define _GLIBCXX_DEBUG
- #endif
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- #ifdef DEBUG
- #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
- #else
- #define eprintf(...) ;
- #endif
- #define sz(x) ((int) (x).size())
- #define TASK "text"
- const int inf = (int) 1.01e9;
- const long long infll = (long long) 1.01e18;
- const ld eps = 1e-9;
- const ld pi = acos((ld) -1);
- #ifdef DEBUG
- mt19937 mrand(300);
- #else
- mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
- #endif
- int rnd(int x) {
- return mrand() % x;
- }
- void precalc() {
- }
- #define ws wwwwwws
- const int maxn = 2005, maxm = 105;
- int c[3];
- int n[2];
- vector<int> g[2][maxn];
- int ws[2][maxn];
- bool read() {
- if (scanf("%d%d%d", &c[0], &c[1], &c[2]) < 3) {
- return false;
- }
- for (int t = 0; t < 2; t++) {
- scanf("%d", &n[t]);
- ws[t][0] = -1;
- for (int v = 0; v < n[t]; v++) {
- g[t][v].clear();
- int k;
- scanf("%d", &k);
- g[t][v].resize(k);
- for (int i = 0; i < k; i++) {
- int u, w;
- scanf("%d%d", &u, &w);
- u--;
- g[t][v][i] = u;
- ws[t][u] = w;
- }
- }
- }
- return true;
- }
- vector<int> path;
- vector<int> ps;
- void getPath(int t, int v) {
- for (int i = 0; i < sz(g[t][v]); i++) {
- int u = g[t][v][i];
- int l = sz(path);
- path.push_back(u);
- ps.push_back(-1);
- getPath(t, u);
- int r = sz(path);
- path.push_back(u);
- ps.push_back(-1);
- ps[l] = r;
- ps[r] = l;
- }
- }
- long long dp[maxn][maxm][maxm];
- long long dpe[maxn][maxm][maxm];
- long long cost(int w0, int w1) {
- return (long long) c[2] * abs(w1 - w0) - (long long) c[1] * w0 - (long long) c[0] * w1;
- }
- void dfs(int v) {
- for (int i = 0; i < sz(path); i++) {
- for (int j = i; j <= sz(path); j++) {
- dp[v][i][j] = 0;
- }
- }
- for (int it = 0; it < sz(g[1][v]); it++) {
- int u = g[1][v][it];
- dfs(u);
- for (int i = sz(path) - 1; i >= 0; i--) {
- for (int j = sz(path); j >= i; j--) {
- auto &cur = dp[v][i][j];
- for (int k = i; k < j; k++) {
- cur = min(cur, dp[v][i][k] + dpe[u][k][j]);
- }
- }
- }
- }
- if (!v) {
- return;
- }
- for (int i = 0; i < sz(path); i++) {
- for (int j = i; j <= sz(path); j++) {
- auto &cur = dpe[v][i][j];
- cur = dp[v][i][j];
- for (int l = i; l < j; l++) {
- int r = ps[l];
- if (r < l || r >= j) {
- continue;
- }
- cur = min(cur, dp[v][l + 1][r] + cost(ws[0][path[l]], ws[1][v]));
- }
- }
- }
- }
- void solve() {
- path.clear();
- ps.clear();
- getPath(0, 0);
- dfs(0);
- long long res = dp[0][0][sz(path)];
- for (int v = 1; v < n[0]; v++) {
- res += (long long) c[1] * ws[0][v];
- }
- for (int v = 1; v < n[1]; v++) {
- res += (long long) c[0] * ws[1][v];
- }
- printf("%lld\n", res);
- }
- int main() {
- precalc();
- #ifdef DEBUG
- assert(freopen(TASK ".in", "r", stdin));
- assert(freopen(TASK ".out", "w", stdout));
- #endif
- while (read()) {
- solve();
- #ifdef DEBUG
- eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
- #endif
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement