結果
問題 | No.95 Alice and Graph |
ユーザー | natsugir |
提出日時 | 2014-12-07 20:16:27 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,278 ms / 5,000 ms |
コード長 | 1,602 bytes |
コンパイル時間 | 774 ms |
コンパイル使用メモリ | 66,256 KB |
実行使用メモリ | 7,752 KB |
最終ジャッジ日時 | 2023-08-09 07:08:15 |
合計ジャッジ時間 | 5,753 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 422 ms
7,752 KB |
testcase_01 | AC | 64 ms
7,644 KB |
testcase_02 | AC | 58 ms
7,440 KB |
testcase_03 | AC | 14 ms
7,544 KB |
testcase_04 | AC | 620 ms
7,560 KB |
testcase_05 | AC | 494 ms
7,528 KB |
testcase_06 | AC | 628 ms
7,616 KB |
testcase_07 | AC | 64 ms
7,632 KB |
testcase_08 | AC | 13 ms
7,612 KB |
testcase_09 | AC | 5 ms
7,532 KB |
testcase_10 | AC | 6 ms
7,432 KB |
testcase_11 | AC | 14 ms
7,540 KB |
testcase_12 | AC | 13 ms
7,612 KB |
testcase_13 | AC | 1,278 ms
7,532 KB |
ソースコード
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0; i<int(n); i++) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++) template<class T> inline T &amin(T &a, T b) { if (a>b) a=b; return a; } template<class T> inline T &amax(T &a, T b) { if (a<b) a=b; return a; } int N, M, K; int FW[60][60]; void init() { scanf("%d%d%d", &N, &M, &K); memset(FW, 0x3f, sizeof FW); REP (i, M) { int x, y; scanf("%d%d", &x, &y); x--; y--; FW[x][y] = FW[y][x] = 1; } REP (i, N) FW[i][i] = 0; } int dp[1<<16][16]; int cost(vector<int> v) { int N = v.size(); memset(dp, 0x3f, sizeof dp); dp[1][0] = 0; REP (S, 1<<N) { REP (i, N) if (S & (1<<i)) { // from REP (j, N) { amin(dp[S | (1<<j)][j], dp[S][i] + FW[v[i]][v[j]]); } } } int ans = dp[(1<<N)-1][0]; REP (i, N) amin(ans, dp[(1<<N)-1][i]); return ans; } int main() { init(); REP (k, N) REP (i, N) REP (j, N) amin(FW[i][j], FW[i][k]+FW[k][j]); // REP (i, N) { // REP (j, N) { // cerr << FW[i][j] << ' ';; // } // cerr << endl; // } vector<int> v(1, 0); for (int i=N-1; i>0; i--) { v.push_back(i); int tmp = cost(v); if (tmp > K) v.pop_back(); if (v.size() == 16u) break; } LL ans = 0; REP (i, v.size()) ans += (1LL<<v[i])-1; cout << ans << endl; return 0; }