Cod sursa(job #2015433)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 august 2017 04:18:09
Problema Tproc Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 4.14 kb
#include <bits/stdc++.h>
using namespace std;

fstream in("tproc.in", ios::in);
fstream out("tproc.out", ios::out);

const int DMAX = 4140;
const int MMAX = 500;
const int NMAX = 500;
const int KMAX = 8;

const int INF = 0x3f3f3f3f;

int dp[MMAX][DMAX], aux[MMAX][DMAX];
int cst[NMAX][NMAX], whg[KMAX + 1];

vector<int> edg[MMAX], lst[MMAX]; vector<int> msk[KMAX];
vector<pair<int, int>> prl[MMAX], cml[MMAX];

void back(int nr, int l, int v, int k) {
    if (l == KMAX)
        return;
    
    for (int i = 0; i < min(v + 1, k); ++i) {
        int nr2 = nr * 10 + i + 1;
        
        msk[l].push_back(nr2);
        back(nr2, l + 1, max(v, i + 1), k);
    }
    
    return;
}

void dfs(int x, int f) {
    int sz1 = (int) lst[x].size() - 1;
    
    for (int i = 0; i < lst[x].size(); ++i)
    for (int j = i + 1; j < lst[x].size(); ++j)
        if (f == -1 or find(lst[f].begin(), lst[f].end(), lst[x][i]) == lst[f].end()
                    or find(lst[f].begin(), lst[f].end(), lst[x][j]) == lst[f].end())
            prl[x].push_back(make_pair(i, j));
    
    if (f != -1) {
        for (int p : lst[x])
            if (find(lst[f].begin(), lst[f].end(), p) != lst[f].end())
                cml[x].push_back(make_pair(
                    find(lst[f].begin(), lst[f].end(), p) - lst[f].begin(),
                    find(lst[x].begin(), lst[x].end(), p) - lst[x].begin()));
    }
    
    if (sz1 == -1) {
        for (int y : edg[x]) {
            if (y == f)
                continue;
        
            dfs(y, x);
            aux[x][0] += aux[y][0];
        }
        
        return;
    }
    
    for (int y : edg[x])
        if (y != f) dfs(y, x);
    
    if (cml[x].size() == 0)
        aux[x][0] = INF;
    else
        memset(aux[x], INF, msk[cml[x].size() - 1].size() * 4);
    
    for (int cnf = 0; cnf < msk[sz1].size(); ++cnf) {
        string axs = to_string(msk[sz1][cnf]);
        for (char &ch : axs) ch -= '0';
        
        for (int y : edg[x]) {
            if (y == f) continue;
            
            int ps = 0, arr = 0;
            int sz2 = (int) cml[y].size() - 1;
            
            for (pair<int, int> pr : cml[y])
                whg[axs[pr.first]] = -1;
            
            for (pair<int, int> pr : cml[y]) {
                if (whg[axs[pr.first]] == -1)
                    whg[axs[pr.first]] = ++ps;
                
                arr = arr * 10 + whg[axs[pr.first]];
            }
            
            if (sz2 != -1)
                ps = (int) (lower_bound(msk[sz2].begin(), msk[sz2].end(), arr) - msk[sz2].begin());
            dp[x][cnf] = min(INF, dp[x][cnf] + aux[y][ps]);
        }
        
        for (pair<int, int> pr : prl[x])
            if (axs[pr.first] == axs[pr.second])
                dp[x][cnf] = min(INF, dp[x][cnf] + cst[lst[x][pr.first]][lst[x][pr.second]]);
        
        int ps = 0, arr = 0;
        int sz2 = (int) cml[x].size() - 1;
        
        for (pair<int, int> pr : cml[x])
            whg[axs[pr.second]] = -1;
        
        for (pair<int, int> pr : cml[x]) {
            if (whg[axs[pr.second]] == -1)
                whg[axs[pr.second]] = ++ps;
            
            arr = arr * 10 + whg[axs[pr.second]];
        }
        
        if (sz2 != -1)
            ps = (int) (lower_bound(msk[sz2].begin(), msk[sz2].end(), arr) - msk[sz2].begin());
        aux[x][ps] = min(aux[x][ps], dp[x][cnf]);
    }
    
    return;
}

int main(void) {
    //clock_t bg, en; bg = clock();
    
    int m, n, k;
    in >> m >> n >> k;
    
    for (int i = 0; i + 1 < m; ++i) {
        int x, y;
        in >> x >> y; --x; --y;
        
        edg[x].push_back(y);
        edg[y].push_back(x);
    }
    
    for (int i = 0; i < m; ++i) {
        int t;
        in >> t;
        
        lst[i].resize(t);
        for (int &x : lst[i])
            in >> x, --x;
        
        sort(lst[i].begin(), lst[i].end());
    }
    
    int p;
    in >> p;
    
    for (int i = 0; i < p; ++i) {
        int x, y, c;
        in >> x >> y >> c; --x; --y;
        cst[x][y] = cst[y][x] = c;
    }
    
    back(0, 0, 0, k);
    dfs(0, -1); out << aux[0][0] << "\n";
    
    //en = clock(); cout << 1.0 * (en - bg) / CLOCKS_PER_SEC;
    return 0;
}