結果
問題 | No.943 取り調べ |
ユーザー |
|
提出日時 | 2019-12-09 07:46:36 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 229 ms / 1,206 ms |
コード長 | 1,557 bytes |
コンパイル時間 | 470 ms |
コンパイル使用メモリ | 44,280 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-11 19:05:50 |
合計ジャッジ時間 | 2,100 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:52:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 52 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:53:70: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 53 | for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &g[i][j]); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:54:42: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 54 | for (int i = 0; i < n; i++) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
bool debug = false; #include <stdio.h> #include <queue> using namespace std; constexpr int kN = 1 << 18, kInf = int(1E9 + 10), kC = 18; int a[kC], g[kC][kC], dp[kN], cost, n, d[kC], td[kC]; bool have[kC], used[kC]; bool ok() { queue<int> q; int nxt; for (int i = 0; i < n; i++) used[i] = have[i] | (d[i] == 0); for (int i = 0; i < n; i++) if (used[i]) q.push(i); for (int i = 0; i < n; i++) td[i] = d[i]; while (!q.empty()) { nxt = q.front(); q.pop(); for (int i = 0; i < n; i++) if (g[i][nxt]) td[i]--; for (int i = 0; i < n; i++) if (td[i] == 0 && !used[i]) { used[i] = true; q.push(i); } } if (debug) { printf("--debug--\n"); for (int i = 0; i < n; i++) printf("%d", have[i] ? 1 : 0); printf("\n"); for (int i = 0; i < n; i++) printf("%d", used[i] ? 1 : 0); printf("\n\n"); } for (int i = 0; i < n; i++) if (!used[i]) return false; return true; } int dfs(int pos) { if (ok()) return cost; if (pos >= n) return kInf; int ans = kInf; for (int i = pos; i < n; i++) { have[i] = true; cost += a[i]; ans = min(ans, dfs(i + 1)); have[i] = false; cost -= a[i]; } return ans; } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &g[i][j]); for (int i = 0; i < n; i++) scanf("%d", &a[i]); for (int i = 0; i < n; i++) d[i] = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (g[i][j] == 1) d[i]++; cost = 0; for (int i = 0; i < n; i++) have[i] = false; printf("%d\n", dfs(0)); }