結果

提出番号	1601
提出者	ecasdqina
言語	C++
提出日時	2018-08-04 13:14:56
問題名	(70)アルゴリズムのお勉強
結果	TLE
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
typedef long long ll;
using std::cout;
using std::endl;
using std::cin;

int n;
std::vector<int> a;
std::vector<std::vector<int>> li;

int dfs(std::vector<int> vec = std::vector<int>(0)) {
	if(vec.size() == n) {
		int ret = 0;
		for(int i = 0; i < n; i++) {
			ret += a[vec[i]];
			
			for(int j = 0; j < i; j++) {
				ret -= li[vec[j]][vec[i]];
			}
		}
		
		return ret;
	}
	
	int mi = 1e9;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < vec.size(); j++) if(vec[j] == i) continue;
		vec.push_back(i);
		mi = std::min(mi, dfs(vec));
		vec.pop_back();
	}
	
	return mi;
}

int main(){
	cin >> n; a.resize(n); li.resize(n, std::vector<int>(n));
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> li[i][j];
	
	cout << dfs() << endl;
	return 0;
}