結果
問題 | No.943 取り調べ |
ユーザー |
![]() |
提出日時 | 2019-12-09 02:24:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 262 ms / 1,206 ms |
コード長 | 1,029 bytes |
コンパイル時間 | 1,863 ms |
コンパイル使用メモリ | 165,400 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2025-01-03 07:34:50 |
合計ジャッジ時間 | 4,353 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int inf = 0x3f3f3f3f; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector< vector<int> > x(n, vector<int>(n)); for (auto&& v : x) { for (auto&& e : v) { cin >> e; } } vector<int> a(n); for (auto&& e : a) { cin >> e; } vector<int> dp(1 << n, inf); dp[0] = 0; for (int S = 1; S != 1 << n; ++S) { for (int i = 0; i != n; ++i) { if (S >> i & 1) { int cost = 0; for (int j = 0; j != n; ++j) { if (x[i][j] and ~S >> j & 1) { bool need = true; for (int k = 0; k != n; ++k) { if (k != i and S >> k & 1) { if (x[k][j]) { need = false; break; } } } if (need) { cost += a[j]; } } } dp[S] = min(dp[S], dp[S ^ 1 << i] + cost); } } } cout << dp.back() << '\n'; }