結果
問題 | No.95 Alice and Graph |
ユーザー |
![]() |
提出日時 | 2020-05-13 18:50:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,251 ms / 5,000 ms |
コード長 | 1,719 bytes |
コンパイル時間 | 1,953 ms |
コンパイル使用メモリ | 174,612 KB |
実行使用メモリ | 7,564 KB |
最終ジャッジ日時 | 2024-09-14 15:36:59 |
合計ジャッジ時間 | 6,081 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; int dp[1 << 16][16]; int main() { int N, M, K; cin >> N >> M >> K; vector<vector<int>> d(N, vector<int>(N, 100)); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; d[a][b] = 1; d[b][a] = 1; } for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } vector<int> use{0}; for (int i = N - 1; i > 0; i--) { vector<int> tmp = use; tmp.push_back(i); bool flag = false; for (int bit = 0; bit < 1 << (int)tmp.size(); bit++) { for (int j = 0; j < (int)tmp.size(); j++) { dp[bit][j] = 100; } } dp[1][0] = 0; for (int bit = 0; bit < 1 << (int)tmp.size(); bit++) { for (int x = 0; x < (int)tmp.size(); x++) { if (bit & 1 << x) { for (int y = 0; y < (int)tmp.size(); y++) { if (bit & 1 << y) { dp[bit][x] = min(dp[bit][x], dp[bit ^ (1 << x)][y] + d[tmp[x]][tmp[y]]); } } } } } for (int j = 0; j < (int)tmp.size(); j++) { if (dp[(1 << (int)tmp.size()) - 1][j] <= K) flag = true; } if (flag) { use = tmp; } if ((int)use.size() == K + 1) { break; } } long long ans = 0; for (auto& x : use) { ans += (1ll << x) - 1; } cout << ans << endl; }