結果

問題 No.95 Alice and Graph
ユーザー krotonkroton
提出日時 2014-12-07 23:58:12
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 377 ms / 5,000 ms
コード長 1,739 bytes
コンパイル時間 720 ms
コンパイル使用メモリ 62,816 KB
実行使用メモリ 9,620 KB
最終ジャッジ日時 2024-11-14 13:29:24
合計ジャッジ時間 2,829 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 198 ms
7,908 KB
testcase_01 AC 31 ms
9,116 KB
testcase_02 AC 31 ms
8,032 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 288 ms
9,620 KB
testcase_05 AC 229 ms
9,144 KB
testcase_06 AC 278 ms
9,564 KB
testcase_07 AC 30 ms
8,688 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 AC 2 ms
6,816 KB
testcase_13 AC 377 ms
9,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int INF = 1 << 28;
const int N_MAX = 66;

int dist[N_MAX][N_MAX];

int dp[1<<18][18];
bool can(vector<int> vs, int K){
    int N = (int)vs.size();
    
    for(int mask=0;mask<1<<N;mask++)for(int i=0;i<N;i++)dp[mask][i] = INF;
    dp[1<<0][0] = 0;
    
    for(int mask=1;mask<1<<N;mask++)for(int last=0;last<N;last++)if(dp[mask][last] != INF){
        for(int next=0;next<N;next++){
            if((mask >> next) & 1)continue;
            
            int v = vs[last];
            int u = vs[next];
            
            dp[mask | (1 << next)][next] = min(dp[mask | (1 << next)][next], dp[mask][last] + dist[v][u]);
        }
    }
    
    for(int last=0;last<N;last++){
        if(dp[(1 << N) - 1][last] <= K)return true;
    }
    
    return false;
}

int main(){
    for(int i=0;i<N_MAX;i++)for(int j=0;j<N_MAX;j++)dist[i][j] = INF;
    for(int i=0;i<N_MAX;i++)dist[i][i] = 0;
    
    int N, M, K;
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int U, V;
        cin >> U >> V;
        
        --U;
        --V;
        
        dist[U][V] = 1;
        dist[V][U] = 1;
    }
    
    for(int k=0;k<N;k++)for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    
    vector<int> use;
    use.push_back(0);
    
    for(int v=N-1;v>0 && use.size() - 1 < K;v--){
        use.push_back(v);
        
        if(!can(use, K)){
            use.pop_back();
        }
    }
    
    ll res = 0;
    for(int v : use){
        res += (1ll << v) - 1;
    }
    
    cout << res << endl;
    return 0;
}
0