解説動画
コード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i) int main() {
int n; cin >> n;
vector<vector> g(n, vector(n, 0)), h(n, vector(n, 0));
int mg;
cin >> mg;
rep(i, mg) {
int u, v;
cin >> u >> v;
u--;
v--;
g[u][v] = 1;
g[v][u] = 1;
}
int mh;
cin >> mh;
rep(i, mh) {
int u, v;
cin >> u >> v;
u--;
v--;
h[u][v] = 1;
h[v][u] = 1;
}
// rep(i, n) {
// rep(j, n) {
// cout << g[i][j] << " ";
// }
// cout << endl;
// }
// cout << "===" << endl;
// rep(i, n) {
// rep(j, n) {
// cout << h[i][j] << " ";
// }
// cout << endl;
// }
vector<vector> a(n, vector(n, 0));
rep(i, n - 1) {
rep(j, n) {
if (j <= i) continue; cin >> a[i][j];
}
}
// rep(i, n - 1) {
// rep(j, n) {
// cout << a[i][j] << " ";
// }
// cout << endl;
// }
vector p(n);
rep(i, n) p[i] = i;
int ans = INT_MAX;
do {
// rep(i, n) cout << p[i] << " ";
// cout << endl;
int now = 0;
rep(i, n) {
rep(j, n) {
if (h[i][j] != g[p[i]][p[j]]) {
now += a[i][j];
}
}
}
ans = min(ans, now);
} while (next_permutation(p.begin(), p.end()));
cout << ans << endl;
return 0;
}
コメント