페이지

2098번: 외판원 순회

https://www.acmicpc.net/problem/2098


#include<cstdio>
#include<algorithm>
using namespace std;
int n, dp[1 << 16][16], w[16][16];
int f(int x, int y) {
    if (x == (1 << n) - 1) return w[y][0] ? w[y][0] : 1e9;
    if (!dp[x][y]) {
        dp[x][y] = 1e9;
        for (int i = 0; i<n; i++) if (w[y][i] && !(x & 1 << i))
            dp[x][y] = min(dp[x][y], f(x | 1 << i, i) + w[y][i]);
    }
    return dp[x][y];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) for (int j = 0; j<n; j++) scanf("%d", &w[i][j]);
    printf("%d", f(1, 0));
    return 0;
}

댓글 없음 :

댓글 쓰기