結果

問題 No.95 Alice and Graph
ユーザー kyuridenamidakyuridenamida
提出日時 2014-12-08 00:55:39
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 555 ms
7,400 KB
testcase_01 AC 1,910 ms
7,392 KB
testcase_02 AC 1,905 ms
7,284 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 363 ms
6,816 KB
testcase_05 AC 280 ms
6,820 KB
testcase_06 AC 377 ms
7,416 KB
testcase_07 AC 1,738 ms
7,404 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 812 ms
6,820 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0