제출 #229991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229991		osaaateiasavtnl	Kronican (COCI16_kronican)	C++14	100 / 100	729 ms	16888 KiB

kronican

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 21;
int a[N][N];
int dp[1 << N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'                                                            
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }   
    }   
    /*
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }   
        }   
    }
    */  
    int all = (1 << n) - 1;
    const int INF = 1e18 + 7;
    for (int i = 0; i < (1 << N); ++i)
        dp[i] = INF;
    dp[all] = 0;
    int ans = INF;
    for (int mask = all; mask >= 0; --mask) {
        if (bp(mask) <= k)
            ans = min(ans, dp[mask]);
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                for (int j = 0; j < n; ++j) {
                    if ((mask >> j) & 1) {
                        if (i != j) {
                            dp[mask ^ (1 << i)] = min(dp[mask ^ (1 << i)], dp[mask] + a[i][j]);
                        }   
                    }   
                }   
            }   
        }   
    }   
    cout << ans << endl;
}

• Subtask 1: 100 / 100