結果

問題 No.95 Alice and Graph
コンテスト
ユーザー なお
提出日時 2014-12-08 02:25:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 776 ms / 5,000 ms
コード長 1,935 bytes
コンパイル時間 1,787 ms
コンパイル使用メモリ 169,100 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-11-14 13:31:34
合計ジャッジ時間 4,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))

const int MAXN = 60;

const int M = 16;
const int INF = 1<<28;
int dp[1<<M][M], dpp[1<<M][M];
// 最短ハミルトンパス
int ShortestHamiltonPath(const vector<vector<int> > &g, int start){
    int n = g.size();
    int N = 1 << n;
    REP(S,N) REP(i,n) dp[S][i] = INF;
    dp[1<<start][start] = 0;
    REP(S,N) REP(i,n){
        if(!(S&(1<<i))) continue;
        REP(j,n){
            if(dp[S|(1<<j)][j] > dp[S][i] + g[i][j]){
                dp[S|(1<<j)][j] = dp[S][i] + g[i][j], dpp[S|(1<<j)][j] = i;
            }
        }
    }
    int t = min_element(dp[N-1], dp[N-1]+n) - dp[N-1];
    if(dp[N-1][t] == INF) return INF; // no route
    return dp[N-1][t];
}

bool check(const vector<vector<int> > &g, const vector<int> &v, int K){
    int n = v.size();
    vector<vector<int> > g2;
    g2.resize(n);
    REP(i,n) g2[i].resize(n,0);
    REP(i,n) REP(j,n){ // ノード番号を圧縮した隣接行列を生成
        g2[i][j] = g[v[i]][v[j]];
    }
    int w = ShortestHamiltonPath(g2, 0);
    return (w <= K);
}

int main(){
    int N,M,K;
    cin >> N >> M >> K;

    vector<vector<int> > g(N, vector<int>(N));
    REP(i,N){
        REP(j,N) g[i][j] = INF;
        g[i][i] = 0;
    }

    REP(i,M){
        int u,v;
        cin >> u >> v; u--;v--;
        g[u][v] = g[v][u] = 1;
    }

    REP(k,N) REP(i,N) REP(j,N){
        g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
    }
    vector<int> v;
    v.push_back(0);
    for(int i = N-1; i > 0; i--){
        if((int)v.size() == K+1) break;
        v.push_back(i);
        if(!check(g, v, K)){
            v.pop_back();
        }
    }
    ll res = 0;
    for(int i = 1; i < (int)v.size(); i++){
        res += (1LL << v[i]) - 1;
    }
    cout << res << endl;
    return 0;
}
0