結果

問題 No.95 Alice and Graph
ユーザー kyuridenamida
提出日時 2014-12-08 00:55:39
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,910 ms / 5,000 ms
コード長 1,353 bytes
コンパイル時間 1,544 ms
コンパイル使用メモリ 162,440 KB
実行使用メモリ 7,416 KB
最終ジャッジ日時 2024-11-14 13:29:45
合計ジャッジ時間 10,331 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//と思ったら僕がバカでしたごめんなさいリバーシのルールを忘れていましたごめんなさい
int wf[60][60];
int dp[16][1<<16];
int tsp(vector<int> u){
    for(int i = 0 ; i < u.size() ; i++)
        for(int j = 0 ; j < (1<<u.size()) ; j++)
            dp[i][j] = 1e9;
    for(int i = 0 ; i < u.size() ; i++)
        dp[i][(1<<i)] = wf[0][u[i]];
    
    for(int i = 0 ; i < (1<<u.size()) ; i++)
        for(int j = 0 ; j < u.size() ; j++)
            for(int k = 0 ; k < u.size() ; k++)
                if( i>>j & 1 ) dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)],dp[j][i]+wf[u[j]][u[k]]);
    int res = 1e9;
    for(int i = 0 ; i < u.size() ; i++)
        res = min(res,dp[i][(1<<u.size())-1]);
    return res;
}
int main(){
    for(int i = 0 ; i < 60 ; i++)
        for(int j = 0 ; j < 60 ; j++)
            wf[i][j] = i==j?0:1e9;
    int N,M,K;
    cin >> N >> M >> K;
    for(int i = 0 ; i < M ; i++){
        int a,b;
        cin >> a >> b;
        a--,b--;
        wf[a][b] = wf[b][a] = 1;
    }
    for(int i = 0 ; i < 60 ; i++)
        for(int j = 0 ; j < 60 ; j++)
            for(int k = 0 ; k < 60 ; k++)
                wf[j][k] = min(wf[j][i]+wf[i][k],wf[j][k]);
    
    
    vector<int> go;
    
    long long res = 0;
    for(int i = N - 1 ; i >= 0 ; i--){
        go.push_back(i);
        if( tsp(go) <= K ){
            res += (1ll<<i) - 1;
        }else go.pop_back();
    }
    cout << res << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0