제출 #415224

#제출 시각아이디문제언어결과실행 시간메모리
415224gromperenKronican (COCI16_kronican)C++14
100 / 100
1061 ms8524 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN = 21; const int inf = 1 << MAXN; int dp[inf]; // dp(pos, not yet schedded (is 1)) int n, k; int c[MAXN][MAXN]; int ans = inf; int solve(int mask) { //cout << mask << endl; if (__builtin_popcount(mask) == k) return 0; if (dp[mask] != -1) return dp[mask]; dp[mask] = inf; for (int i = 0; i < n; ++i) { if ((mask & (1 << i)) == 0) continue; for (int j = 0; j < n; ++j) { if (i == j) continue; if ((mask & (1 << j)) == 0) continue; dp[mask] = min(dp[mask], solve(mask ^ (1 << i)) + c[i][j]); } } return dp[mask]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); memset(dp, -1, sizeof(dp)); cin >> n >> k; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> c[i][j]; } } cout << solve((1 << n) - 1) << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...