boj_2098

2098.cpp

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 0x3c3c3c3c;
int n, w[16][16], dp[1<<16][16];
int main() {
	scanf("%d",&n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			scanf("%d", &w[i][j]);
	memset(dp, 0x3c, sizeof(dp)); // dp를 0x3c3c3c3c=1010580540로 초기화(무한대 취급)
	dp[1][0]=0; // => dp[00...001][0] = 0
	for(int state=1; state<(1<<n); state++)
		for(int last=0; last<n; last++) {
        		if(!((state>>last) & 1)) continue; // last는 반드시 state에 포함되어 있어야 함
        		for(int k=0; k<n; k++)
                		if(!((state>>k) & 1) && w[last][k] != 0) // k가 방문되지 않은 정점이고 last에서 k로 이동 가능한지 확인
                			dp[state|(1<<k)][k]=min(dp[state|(1<<k)][k], dp[state][last] + w[last][k]);
       		}
    	int ret = INF;
    	for(int i=1; i<n; i++)
    		if(w[i][0] != -1) // i번 정점 -> 0번 정점으로 이동 가능한지 확인
    			ret = min(ret, dp[(1<<n)-1][i] + w[i][0]);
    	printf("%d", ret);
    	return 0;
}