Pagini recente » Borderou de evaluare (job #2618660) | Cod sursa (job #448933) | Borderou de evaluare (job #333746) | Cod sursa (job #2127820) | Cod sursa (job #1312063)
#include <fstream>
#include <algorithm>
#define DIM 15
#define INF 2000000005
#define infile "cast.in"
#define outfile "cast.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int n, t;
int cost[DIM][DIM], dp[DIM][1 << DIM];
int solve(int elem, int config) {
if (dp[elem][config] != INF)
return dp[elem][config];
int res = INF;
for (int new_elem = 0; new_elem < n; ++new_elem) {
if (!(config & (1 << new_elem)) || new_elem == elem)
continue;
res = std::min(res, cost[elem][new_elem] + solve(elem, config ^ (1 << new_elem)));
int temp = (config ^ (1 << elem) ^ (1 << new_elem));
for (int old_config = temp; old_config; (--old_config) &= temp)
res = std::min(res, cost[elem][new_elem] + std::max(solve(elem, config ^ old_config ^ (1 << new_elem)), solve(elem, old_config ^ (1 << new_elem))));
}
dp[elem][config] = res;
return res;
}
int main() {
f >> t;
for (; t; --t) {
f >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
f >> cost[i][j];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < (1 << n); ++j)
dp[i][j] = INF;
dp[i][1 << i] = 0;
}
g << solve(0, (1 << n) - 1) << "\n";
}
return 0;
}
//Trust me, I'm the Doctor!