제출 #1342127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1342127		rodddd	Kronican (COCI16_kronican)	C++20	0 / 100	2097 ms	86596 KiB

kronican

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9+10;
const int maxn = 21;
const int maxm = (1<<20)+5;

int n, k;

int d[maxn][maxn];

void floyd_warshall(){
    for(int k=0; k<n; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
}

int dp[maxm][maxn];

int solve(int mask, int i, int total, bool first){
    if(total >= (n-k+1)) return dp[mask][i] = 0;
    
    if(mask == (1 << n) -1) return dp[mask][i] = inf;
    
    if(dp[mask][i] != -1) return dp[mask][i];
    
    int ans=inf;
    for(int v=0; v<n; v++){
        if(mask & (1<<v) || (d[i][v]==-1 && !first)) continue;
        if(first) d[i][v] = 0;
        
        int curr = inf;
        for(int u=0; u<n; u++){
            if(mask & (1<<u)) continue;
            curr = min(curr, (solve(mask | (1<<u), u, total+1, false)+d[i][v]));
        }
        
        ans = min(ans, curr);
    }
    
    return dp[mask][i] = ans;
}

int main() {
	cin >> n >> k;

	memset(dp, -1, sizeof(dp));
	memset(d, -1, sizeof(d));
	for(int i=0; i<n; i++){
	    for(int j=0; j<n; j++){
	        cin >> d[i][j];
	    }
	}
	
	floyd_warshall();
    
    int ans= solve(0, n, 0, true);
    
    cout << ans << "\n";
}

• Subtask 1: 0 / 100