1 条题解
-
1
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; #define X first #define Y second #define MP make_pair typedef pair<int, int> PII; const int N = 15, M = 2000010; const int INF = 0x3f3f3f3f; int n, k, m, P[N], deg[N], dis[N][N], f[1 << N], g[M]; bool vis[M]; vector<PII> G[N]; int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar(); while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } void Pre_Work(){ memset(dis, 0x3f, sizeof(dis)); for(int i = 1; i <= n; i ++) dis[i][i] = 0; P[0] = 1; for(int i = 1; i <= n; i ++) P[i] = P[i - 1] * 3; } void Get_Map(){ memset(g, 0x3f, sizeof(g)); g[2] = 0; queue<int> q; q.push(2); while(!q.empty()){ int s = q.front(); q.pop(); vis[s] = false; for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0) for(int i = 0; i < (int) G[u].size(); i ++){ int v = G[u][i].X; if((s / P[v]) % 3 == 0){ int t = s + P[v] * 2; if(g[t] > g[s]){ g[t] = g[s]; if(!vis[t]) q.push(t), vis[t] = true; } } } for(int u = 0; u < n; u ++) if((s / P[u]) % 3 > 0) for(int v = 0; v < n; v ++) if((s / P[v]) % 3 == 0){ int t = s + P[v]; t += ((s / P[u]) % 3 == 1) ? P[u] : - P[u]; if(g[t] > g[s] + dis[u][v]){ g[t] = g[s] + dis[u][v]; if(!vis[t]) q.push(t), vis[t] = true; } } } } void Get_Dis(){ memset(f, 0x3f, sizeof(f)); f[0] = 0; for(int s = 0; s < (1 << n); s ++) for(int u = 0; u < n; u ++) if(!(s >> u & 1)) for(int v = u + 1; v < n; v ++) if(!(s >> v & 1)){ int t = s + (1 << u) + (1 << v); f[t] = min(f[t], f[s] + dis[u][v]); } } int main(){ n = read(), k = read(); Pre_Work(); int sum = 0; for(int i = 1; i <= k; i ++){ int u = read() - 1, v = read() - 1, w = read(); G[u].push_back(MP(v, w)); G[v].push_back(MP(u, w)); dis[u][v] = dis[v][u] = min(dis[u][v], w); deg[u] ++, deg[v] ++; sum += w; } m = read(); for(int i = 1; i <= m; i ++){ int u = read() - 1, v = read() - 1, w = read(); dis[u][v] = dis[v][u] = min(dis[u][v], w); } for(int k = 0; k < n; k ++) for(int i = 0; i < n; i ++) if(dis[i][k] != INF) for(int j = 0; j < n; j ++) if(dis[k][j] != INF) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); Get_Map(); Get_Dis(); int ans = INF; for(int i = 0; i < P[n]; i ++){ int s = i; bool flag = false; for(int u = 0; u < n; u ++) if(G[u].size() && !((s / P[u]) % 3)) {flag = true; break;} if(flag) continue; for(int u = 0; u < n; u ++) if(deg[u] & 1) s += ((i / P[u]) % 3 == 1) ? P[u] : - P[u]; int t = 0; for(int u = 0; u < n; u ++) if((s / P[u]) % 3 == 1) t += (1 << u); ans = min(ans, g[i] + f[t]); } printf("%d\n", ans + sum); return 0; }
- 1
信息
- ID
- 5000
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者