結果

問題 No.95 Alice and Graph
ユーザー kyuridenamidakyuridenamida
提出日時 2014-12-08 00:55:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,926 ms / 5,000 ms
コード長 1,353 bytes
コンパイル時間 1,425 ms
コンパイル使用メモリ 161,108 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-04-26 21:55:12
合計ジャッジ時間 10,570 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 558 ms
7,552 KB
testcase_01 AC 1,890 ms
7,520 KB
testcase_02 AC 1,926 ms
7,424 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 365 ms
5,376 KB
testcase_05 AC 282 ms
5,376 KB
testcase_06 AC 376 ms
7,552 KB
testcase_07 AC 1,742 ms
7,536 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 829 ms
5,632 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