C++11(clang++ 3.9) 解法, 执行用时: 450ms, 内存消耗: 8680K, 提交时间: 2019-04-23 11:04:07

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
int ri() {
    char ch = getchar(); int x = 0;
    for(;ch < '0' || ch > '9'; ch = getchar()) ;
    for(;ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) - '0' + ch;
    return x;
}
const int N = 14, M = 110, S = 8192, pS = 1594323, inf = 0x3f3f3f3f;
int h[N][N], a[N], d[N], g[S], f[pS], q[pS], nx[M], to[M], pr[N], p[N], bin[N], n, tp, ans;
void add(int u, int v) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp;}
void adds(int u, int v) {add(u, v); add(v, u); d[u] ^= 1; d[v] ^= 1;}
int b(int s, int x) {return s / p[x] % 3;}
int c(int s, int x) {return s + (b(s, x) == 1 ? p[x] : -p[x]);}
int Up(int &a, int b) {return a < b ? a : a = b;}
void Pre() {
    bin[0] = 1; p[0] = 1; rep(i, 1, n) bin[i] = bin[i - 1] << 1, p[i] = p[i - 1] * 3;
    rep(k, 1, n) rep(i, 1, n) if(k != i) rep(j, 1, n) if(k != j && j != i)
        Up(h[i][j], h[i][k] + h[k][j]);
    memset(g, 0x3f, sizeof(g)); g[0] = 0; 
    rep(s, 0, bin[n] - 1) rep(i, 1, n) if(~s & bin[i - 1]) rep(j, i + 1, n) if(~s & bin[j - 1])
        Up(g[s ^ bin[i - 1] ^ bin[j - 1]], g[s] + h[i][j]);
}
void Dp() {
    memset(f, 0x3f, sizeof(f)); f[2] = 0; int L = 0, R; q[R = 1] = 2;
    for(int s = q[++L], tp = 0; L <= R; s = q[++L], tp = 0) {
        rep(i, 1, n) if(b(s, i - 1)) a[++tp] = i;
        rep(u, 1, n) if(!b(s, u - 1)) {
            int t = s + p[u - 1] * 2;
            for(int i = pr[u]; i; i = nx[i]) if(b(s, to[i] - 1))
                {if(f[t] == inf) q[++R] = t; Up(f[t], f[s]);}
            rep(i, 1, tp) if(h[a[i]][u] != inf) {
                t = c(s, a[i] - 1) + p[u - 1]; if(f[t] == inf) q[++R] = t;
                Up(f[t], f[s] + h[a[i]][u]);
            }
        }
    }
}
bool check(int s) {rep(i, 1, n) if(pr[i] && !b(s, i - 1)) return false; return true;}
void Calc() {
    ans = inf;
    rep(s, 0, p[n] - 1) if(check(s)) {
        int t = 0;
        rep(i, 1, n) if(d[i] ^ (2 - b(s, i - 1) & 1)) t |= bin[i - 1];
        Up(ans, f[s] + g[t]);
    }
}
int main() {
    n = ri(); memset(h, 0x3f, sizeof(h)); int W = 0;
    for(int k = ri();k--;) {
        int u = ri(), v = ri(), w = ri(); adds(u, v); 
        h[v][u] = Up(h[u][v], w); W += w;
    }
    for(int k = ri();k--;) {
        int u = ri(), v = ri(), w = ri();
        h[v][u] = Up(h[u][v], w);
    }
    Pre(); Dp(); Calc(); printf("%d\n", ans + W);
    return 0;
}