結果

問題 No.95 Alice and Graph
コンテスト
ユーザー kroton
提出日時 2014-12-07 23:58:12
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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